广州网站建设公司嘉御,建设银行苏州网站,义乌外贸网站建设,邯郸房产信息网查询系统算法#xff1a;
前序、中序、后序都可以#xff0c;这道题正常逻辑一般都是用前序
正确代码#xff1a;
这里就是在root1这颗树上改的#xff0c;也可以新建一个树。
/*** Definition for a binary tree node.* public class TreeNode {* int val;* TreeNode …
算法
前序、中序、后序都可以这道题正常逻辑一般都是用前序
正确代码
这里就是在root1这颗树上改的也可以新建一个树。
/*** Definition for a binary tree node.* public class TreeNode {* int val;* TreeNode left;* TreeNode right;* TreeNode() {}* TreeNode(int val) { this.val val; }* TreeNode(int val, TreeNode left, TreeNode right) {* this.val val;* this.left left;* this.right right;* }* }*/
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;}
}
时间空间复杂度
时间复杂度分析
在每个节点上只进行了常数时间的操作比如节点值的相加和指针的赋值。因此每个节点的操作时间复杂度为 O(1)。在最坏情况下需要遍历两棵树的所有节点。因此整个合并过程的时间复杂度为O(n)其中 n 是两棵树中节点的总数。
空间复杂度分析
递归调用的深度最坏情况下为树的高度因此空间复杂度为O(ℎ)其中 ℎ 是树的高度。在最坏情况下如果树是完全不平衡的高度可以达到 n其中 n 是树中节点的总数。因此空间复杂度为O(n)。
因此该算法的时间复杂度为O(n)空间复杂度为O(n)。
