购物网站开发中遇到的问题,商标设计网站猪八戒,自动seo网站源码,软文素材库文章目录 Merge Two Binary Trees 合并二叉树问题描述#xff1a;分析代码PreOrder DFSPreOrder Tag Merge Two Binary Trees 合并二叉树
问题描述#xff1a;
给你两棵二叉树#xff1a; root1 和 root2 。
想象一下#xff0c;当你将其中一棵覆盖到另一棵之上时#… 文章目录 Merge Two Binary Trees 合并二叉树问题描述分析代码PreOrder DFSPreOrder Tag Merge Two Binary Trees 合并二叉树
问题描述
给你两棵二叉树 root1 和 root2 。
想象一下当你将其中一棵覆盖到另一棵之上时两棵树上的一些节点将会重叠而另一些不会。你需要将这两棵树合并成一棵新二叉树。合并的规则是如果两个节点重叠那么将这两个节点的值相加作为合并后节点的新值否则不为 null 的节点将直接作为新二叉树的节点。
返回合并后的二叉树。
注意: 合并过程必须从两个树的根节点开始。 两棵树中的节点数目在范围 [ 0 , 2000 ] 内 − 1 0 4 N o d e . v a l 1 0 4 两棵树中的节点数目在范围 [0, 2000] 内\\ -10^4 Node.val 10^4 两棵树中的节点数目在范围[0,2000]内−104Node.val104
分析 目标是将2个树进行覆盖可以合并到第3个树上也可以将tree2合并到tree1. 而且是要求相同的位置进行merge所以必然要对树进行遍历。
其中最简单的就是前序递归细节就不说了all in code.
相对于递归的方法比较容易想到迭代的实现方式也有很多所以有点绕。
代码 PreOrder DFS
public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {if(root1null||root2null){return root1null?root2:root1;} root1.val root2.val;root1.left mergeTrees(root1.left,root2.left);root1.right mergeTrees(root1.right,root2.right);return root1;}时间复杂度 O ( m i n ( M N ) O(min(MN) O(min(MN)
空间复杂度 O ( H ) O(H) O(H)
PreOrder
public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {if(root1null||root2null){return root1null?root2:root1;} DequeTreeNode[] 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!nullr2!null){queue.offerLast(new TreeNode[]{r1,r2});}if(l1!nulll2!null){queue.offerLast(new TreeNode[]{l1,l2});}if(l1null||l2null){p1.left l1null? l2:l1;} if(r1null||r2null){ p1.right r1null? r2:r1;} } return root1;}
时间复杂度 O ( m i n ( M N ) O(min(MN) O(min(MN)
空间复杂度 O ( H ) O(H) O(H)
Tag
Tree
DFS
