php是用来做网站的吗,各类东莞微信网站建设,网站诊断,微商城网站建设市场本文是力扣LeeCode-617、合并二叉树【二叉树DFS】 学习与理解过程#xff0c;本文仅做学习之用#xff0c;对本题感兴趣的小伙伴可以出门左拐LeeCode。
给你两棵二叉树#xff1a; root1 和 root2 。
想象一下#xff0c;当你将其中一棵覆盖到另一棵之上时#xff0c;两…本文是力扣LeeCode-617、合并二叉树【二叉树DFS】 学习与理解过程本文仅做学习之用对本题感兴趣的小伙伴可以出门左拐LeeCode。
给你两棵二叉树 root1 和 root2 。
想象一下当你将其中一棵覆盖到另一棵之上时两棵树上的一些节点将会重叠而另一些不会。你需要将这两棵树合并成一棵新二叉树。合并的规则是如果两个节点重叠那么将这两个节点的值相加作为合并后节点的新值否则不为 null 的节点将直接作为新二叉树的节点。
返回合并后的二叉树。
注意: 合并过程必须从两个树的根节点开始。
示例 1 输入root1 [1,3,2,5], root2 [2,1,3,null,4,null,7] 输出[3,4,5,5,4,null,7] 示例 2 输入root1 [1], root2 [1,2] 输出[2,2] 提示
两棵树中的节点数目在范围 [0, 2000] 内-10^4 Node.val 10^4
思路
递归法
本题使⽤前中后遍历都是可以的
1. 确定递归函数的参数和返回值 直接使用原题目的即可
2. 确定终⽌条件
传⼊了两个树那么就有两个树遍历的节点t1 和 t2
无论t1 null或者t2 null合并后都会由不为null的一方取代若t1 和 t2都等于null则返回null即可 if (root1null)return root2;if (root2null)return root1;3. 确定单层递归的逻辑
我们重复利⽤⼀下t1这个树t1就是合并之后树的根节点。那么单层递归中就要把两棵树的元素加到⼀起。t1-val t2-valt1 的左⼦树是合并 t1左⼦树 t2左⼦树之后的左⼦树。t1 的右⼦树是合并 t1右⼦树 t2右⼦树之后的右⼦树。 最终t1就是合并之后的根节点。 root1.valroot2.val;root1.left mergeTrees(root1.left,root2.left);root1.right mergeTrees(root1.right,root2.right);return root1;完整代码
class Solution {public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {if (root1null)return root2; // 如果t1为空合并之后就应该是t2if (root2null)return root1; // 如果t2为空合并之后就应该是t1// 修改了t1的数值和结构root1.valroot2.val; //中root1.left mergeTrees(root1.left,root2.left); //左root1.right mergeTrees(root1.right,root2.right); //右return root1;}
}最重要的一句话做二叉树的题目首先需要确认的是遍历顺序 大佬们有更好的方法请不吝赐教谢谢
