成都有哪些做网站开发的大公司,中国公司查询网站,网站制作公司网站源码,贵州省城乡与住房建设厅网站文章目录 1 题目描述2 思路优化代码完整输入输出 参考 1 题目描述
https://leetcode.cn/problems/merge-two-binary-trees/description/
给你两棵二叉树#xff1a; root1 和 root2 。
将其中一棵覆盖到另一棵之上时#xff0c;两棵树上的一些节点将会重叠#xff08;而另… 文章目录 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( );ListTreeNode nodes1 getTree(strNums1);ListTreeNode nodes2 getTree(strNums2);// 构建二叉树TreeNode root1 constructTree(nodes1);TreeNode root2 constructTree(nodes2);//TreeNode root solution.mergeTrees(root1, root2);// 展示结果preorderTree(root);}}public static ListTreeNode getTree(String[] strNums) {if (strNums.length 0) return null;ListTreeNode 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(ListTreeNode 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
