合并二叉树 Posted on 2021-06-23 00:00:00 2021-06-26 00:00:00 by Author 摘要 给定两颗二叉树，你能把它们合并起来吗？？？？？？ # 合并二叉树 1. 题目描述 - 给定两个二叉树，想象当你将它们中的一个覆盖到另一个上时，两个二叉树的一些节点便会重叠。 你需要将他们合并为一个新的二叉树。合并的规则是如果两个节点重叠，那么将他们的值相加作为节点合并后的新值，否则不为 NULL 的节点将直接作为新二叉树的节点。 2. 示例描述 - 示例一 > 输入: > Tree 1 Tree 2 > 1 2 > / \ / \ > 3 2 1 3 > / \ \ > 5 4 7 > 输出: > 合并后的树: > 3 > / \ > 4 5 > / \ \ > 5 4 7 3. 解题思路 - 对于本道题，也是构造二叉树的一道题目，大家在看完[中序与后序遍历构造二叉树](http://www.geticsen.cn/view/articles/detail/6e6ebd35-d8d3-46e5-a4d7-3e2c63b6cf92 "中序与后序遍历构造二叉树")和[最大二叉树](http://www.geticsen.cn/view/articles/detail/91e998d8-6405-4270-a45d-6e1c68ac1295 "最大二叉树")这两篇文章后，那么实现本道题，那简直就是得心应手啊！！！！那么怎么实现尼，首先给定的两棵二叉树要遍历，不遍历怎么知道该怎么合并。所以选择遍历的方式，这里选用先序遍历的方式，对于每一次递归遍历的时候，我们判断此时递归所给的两个节点如果不为空，那么构造这个节点的时候，该节点的值就是所给节点值得和，如果其中一个不为空，那么就构造一个节点，构造节点得值为不为空的节点值，如果递归所给的两个节点的值为空，那么本次递归结束。直到完全遍历完这两个棵二叉树之后，也就构造完成。 - 大家可以先看看前几篇构造二叉树的文章，看完之后再来看看本篇文章，就会发现其中的解题套路了。本题代码如下所示。 4. 代码示例 ```java public TreeNode mergeTrees(TreeNode root1, TreeNode root2) { //如果所给的节点都为null,那么本次递归结束，没有需要合并的节点了 if (root1 == null && root2 == null) return null; else { //两个都不为空，或者其中一个不为空，那么就构造一个节点 int temp = 0; if (root1 != null) temp += root1.val; if (root2 != null) temp += root2.val; TreeNode treeNode = new TreeNode(temp); //继续递归构造该节点的左子树 //递归中的参数，使用了条件表达式的写法，主要是为了防止出现空指针异常的情况 treeNode.left = mergeTrees(root1 != null ? root1.left : null, root2 != null ? root2.left : null); //继续递归构造该节点的右子树 //同样递归中的参数，使用了条件表达式的写法，主要是为了防止出现空指针异常的情况 treeNode.right = mergeTrees(root1 != null ? root1.right : null, root2 != null ? root2.right : null); //最后返回构造好的节点 return treeNode; } } ```
{{ item.content }}
{{ child.content }}