Leetcode 617. Merge Two Binary Trees(python)

题目

解法1：DFS

在recursion的每一步

• 如果当前的两个节点都不为空，更新第一棵树的当前节点val为两个节点val的和
• 如果其中有一个节点为空，则返回另一个节点
• 当前节点的left和right节点为下一层recursion返回的结果

class Solution(object):def mergeTrees(self, t1, t2):""":type t1: TreeNode:type t2: TreeNode:rtype: TreeNode"""if not t1:return t2if not t2:return t1t1.val += t2.valt1.left = self.mergeTrees(t1.left,t2.left)t1.right = self.mergeTrees(t1.right,t2.right)return t1

** 时间复杂度**：O(n),n代表两棵树节点个数中的较小值，因为只有在两棵树的对应节点都不为空时才需要将两个节点的值相加，不然就是直接返回结果
空间复杂度：O(n),这是官方给出的空间复杂度，但是我不太明白为什么这边的recursion会需要额外的空间复杂度而不是O(1),因为我们所有的更新操作都是在其中一颗树上完成的，并没有开辟额外空间，欢迎知道的小伙伴留言

解法2：BFS

• 建立一个堆栈，储存元素为两棵树对应节点pair
• 如果第一棵树某个节点为空而另一棵树对应节点不为空，直接把另一棵树的节点替换第一棵树的空节点
• 否则的话，将第一棵树的节点值更新为两个节点值的和

class Solution(object):def mergeTrees(self, t1, t2):""":type t1: TreeNode:type t2: TreeNode:rtype: TreeNode"""if not t1:return t2if not t2:return t1stack = [[t1,t2]]while stack:node1,node2 = stack.pop()if not node2:continuenode1.val += node2.valif not node1.left:node1.left = node2.leftelse:stack.append((node1.left,node2.left))if not node1.right:node1.right = node2.rightelse:stack.append((node1.right,node2.right))return t1

稍微改进了一下，总觉得这个continue操作让人不爽，改成只有两个节点都不为空才压栈，因为其实第二棵树某个节点为空时并不需要压栈。然而其实对于时间复杂度并没有改进，只是个人癖好，所以习惯第一种方法的小伙伴就忽略好了

class Solution(object):def mergeTrees(self, t1, t2):""":type t1: TreeNode:type t2: TreeNode:rtype: TreeNode"""    if not t1:return t2if not t2:return t1stack = [[t1,t2]]while stack:node1,node2 = stack.pop()# if not node2:# continuenode1.val += node2.valif not node1.left:node1.left = node2.leftelif node1.left and node2.left:stack.append((node1.left,node2.left))if not node1.right:node1.right = node2.rightelif node1.right and node2.right:stack.append((node1.right,node2.right))return t1

时间复杂度：O(n), n为较小的树的总结点数
空间复杂度：O(n)

另外，这俩方法都值超过了百分之30多的提交，不知道还有什么更快的方法，有更好方法的同学欢迎指教