【LeetCode 算法】Merge Two Binary Trees 合并二叉树

Merge Two Binary Trees 合并二叉树

问题描述：

给你两棵二叉树： root1 和 root2 。

想象一下，当你将其中一棵覆盖到另一棵之上时，两棵树上的一些节点将会重叠（而另一些不会）。你需要将这两棵树合并成一棵新二叉树。合并的规则是：如果两个节点重叠，那么将这两个节点的值相加作为合并后节点的新值；否则，不为 null 的节点将直接作为新二叉树的节点。

返回合并后的二叉树。

注意: 合并过程必须从两个树的根节点开始。

$$\begin{gathered} 两棵树中的节点数目在范围[0,2000]内 \\ -10^4<=Node.val<=10^4 \end{gathered}$$

分析

目标是将2个树，进行覆盖，可以合并到第3个树上，也可以将tree2合并到tree1.

而且是要求相同的位置进行merge，所以必然要对树进行遍历。

其中最简单的就是前序递归，细节就不说了，all in code.

相对于递归的方法比较容易想到，迭代的实现方式也有很多，所以有点绕。

代码

PreOrder DFS

public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {if(root1==null||root2==null){return root1==null?root2:root1;} root1.val += root2.val;root1.left = mergeTrees(root1.left,root2.left);root1.right = mergeTrees(root1.right,root2.right);return root1;}

时间复杂度$O(min(M+N)$

空间复杂度$O(H)$

PreOrder

public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {if(root1==null||root2==null){return root1==null?root2:root1;} Deque<TreeNode[]> queue = new ArrayDeque();queue.offerLast(new TreeNode[]{root1,root2});while(!queue.isEmpty()){TreeNode[] t = queue.pollLast();TreeNode p1 = t[0],p2 =t[1];p1.val+= p2.val;TreeNode l1 = p1.left,l2 = p2.left;TreeNode r1 = p1.right,r2 = p2.right; if(r1!=null&&r2!=null){queue.offerLast(new TreeNode[]{r1,r2});}if(l1!=null&&l2!=null){queue.offerLast(new TreeNode[]{l1,l2});}if(l1==null||l2==null){p1.left = l1==null? l2:l1;} if(r1==null||r2==null){                p1.right = r1==null? r2:r1;} } return root1;}

时间复杂度$O(min(M+N)$

空间复杂度$O(H)$

Tag

Tree

DFS