当前位置：首页 > news >正文

LC617-合并二叉树

news 来源：原创 2024/9/20 9:37:20

文章目录

1 题目描述
2 思路
- 优化代码
- 完整输入输出
参考

1 题目描述

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

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

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

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

返回合并后的二叉树。

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

在这里插入图片描述

2 思路

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

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

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

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*/