LC617-合并二叉树

1 题目描述

https://leetcode.cn/problems/merge-two-binary-trees/description/

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

将其中一棵覆盖到另一棵之上时，两棵树上的一些节点将会重叠（而另一些不会）。你需要将这两棵树合并成一棵新二叉树。
合并的规则是：

• 如果两个节点重叠，那么将这两个节点的值相加作为合并后节点的新值；
• 否则，不为 null 的节点将直接作为新二叉树的节点。

返回合并后的二叉树。

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

2 思路

合并二叉树需要遍历整个树：考虑使用递归遍历

合并多个树，使用递归三部曲：

1. 确定函数的返回值和参数：返回值，构建好的树；参数，需要构建的两个树
2. 确定递归结束的条件：
   • 当两个叔都是空的时候，返回空（空）
   • 左子树为空，返回右子树；同样的，右子树为空，返回左子树
3. 递归的逻辑：
   • 当左右子树都不为空的时候，将两个节点的值相加，然后赋值给一个子树
   • 递归构建左右子树

class Solution{public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {// 递归结束的条件if (root1 == null && root2 == null) {return null;} else if (root1 != null && root2 == null) {return root1;} else if (root1 == null  && root2 != null) {return root2;}// 递归逻辑root1.val += root2.val;root1.left = mergeTrees(root1.left, root2.left);root1.right = mergeTrees(root1.right, root2.right);// 最终的结果return root1;}}

优化代码

对于递归结束的条件，可以进行代码优化；返回树的逻辑可以为：如果一颗树为空，则返回另外一颗，如果领一颗是null则直接结束；如果不是null，则进行了连接

class Solution{public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {// 递归结束的条件if (root1 == null) {return root2;}if (root2 == null) {return root1;}// 递归逻辑root1.val += root2.val;root1.left = mergeTrees(root1.left, root2.left);root1.right = mergeTrees(root1.right, root2.right);// 最终的结果return root1;}}

完整输入输出

• 使用List存储输入的元素
• 使用递归构建二叉树

import java.util.*;class TreeNode{int val;TreeNode left;TreeNode right;public TreeNode() {}public TreeNode(int val) {this.val = val; }public TreeNode(int val, TreeNode left, TreeNode right) {this.val = val;this.left = left;this.right = right;}}// Solutionpublic class Main {public static void main(String[] args) {// 递归构建二叉树Scanner in = new Scanner(System.in);Solution solution = new Solution();while (in.hasNext()) {String[] strNums1 = in.nextLine().split(" ");String[] strNums2  = in.nextLine().split(" ");List<TreeNode> nodes1 = getTree(strNums1);List<TreeNode> nodes2 = getTree(strNums2);// 构建二叉树TreeNode root1 = constructTree(nodes1);TreeNode root2 = constructTree(nodes2);//TreeNode root = solution.mergeTrees(root1, root2);// 展示结果preorderTree(root);}}public static List<TreeNode> getTree(String[] strNums) {if (strNums.length == 0) return null;List<TreeNode> nodes = new LinkedList<>();for (String strNum: strNums) {if (!strNum.isEmpty()) {if (strNum.equals("null")) {nodes.add(null);} else {nodes.add(new TreeNode(Integer.parseInt(strNum)));}}}return nodes;}public static TreeNode constructTree(List<TreeNode> nodes) {if (!nodes.isEmpty()) {TreeNode node = nodes.remove(0);if (node != null) {node.left = constructTree(nodes);node.right = constructTree(nodes);}return node;}return null;}public static void preorderTree(TreeNode root) {if (root != null) {System.out.print(root.val + " ");preorderTree(root.left);preorderTree(root.right);}}
}
/*
test case:
1 3 5 null null null 2
2 1 null 4 null null 3 null 7r = 3 4 5 4 5 7*/

---

参考

https://www.programmercarl.com/0617.合并二叉树.html