石家庄网站建设公司wsjz,怎么创建私人网站,企业管理六大体系,如何用ps制作网站文章目录 题目思路代码 题目
617. 合并二叉树
难度#xff1a; 简单
描述#xff1a;
给你两棵二叉树#xff1a; root1 和 root2 。 想象一下#xff0c;当你将其中一棵覆盖到另一棵之上时#xff0c;两棵树上的一些节点将会重叠#xff08;而另一些不会#xff0… 文章目录 题目思路代码 题目
617. 合并二叉树
难度 简单
描述
给你两棵二叉树 root1 和 root2 。 想象一下当你将其中一棵覆盖到另一棵之上时两棵树上的一些节点将会重叠而另一些不会。你需要将这两棵树合并成一棵新二叉树。合并的规则是如果两个节点重叠那么将这两个节点的值相加作为合并后节点的新值否则不为 null 的节点将直接作为新二叉树的节点。
返回合并后的二叉树。
注意: 合并过程必须从两个树的根节点开始。
示例 1 输入root1 [1,3,2,5], root2 [2,1,3,null,4,null,7] 输出[3,4,5,5,4,null,7] 示例 2 输入root1 [1], root2 [1,2] 输出[2,2] 提示 两棵树中的节点数目在范围 [0, 2000] 内 -104 Node.val 104思路
时间复杂度分析对于树的话一般使用dfs或者bfs进行解题只有当两个树的节点都不为空的时候才进行和并所有时间复杂度不会超过两颗树中节点最少得那棵树所以为O(min(m,n)) 空间复杂度 空间复杂度取决于递归调用的层数递归调用的层数不会超过两棵树中较小的以防的二叉树的高度最坏情况为节点数为树的深度所以为O(min(m,n)) 解法思路使用递归来实现dfs或者使用队列辅助来实现bfs都可以解答
代码
首先定义TreeNode: 这个要会写
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;}
}深度优先遍历 使用递归来进行实现 //合并二叉树public static void main(String[] args) {}//深度优先遍历public TreeNode mergeTrees(TreeNode t1,TreeNode t2){if(t1 null){return t2;}if(t2 null){return t1;}TreeNode merged new TreeNode(t1.valt2.val);merged.left mergeTrees(t1.left,t2.left);merged.right mergeTrees(t1.right,t2.right);return merged;}广度优先遍历
//广度优先遍历public TreeNode mergeTrees1(TreeNode t1,TreeNode t2){if(t1 null){return t2;}if(t2 null){return t1;}TreeNode merged new TreeNode(t1.valt2.val);QueueTreeNode queue new LinkedListTreeNode();QueueTreeNode queue1 new LinkedListTreeNode();QueueTreeNode queue2 new LinkedListTreeNode();queue.offer(merged);queue1.offer(t1);queue2.offer(t2);while(!queue1.isEmpty() !queue2.isEmpty()){TreeNode node queue.poll();TreeNode node1 queue1.poll();TreeNode node2 queue2.poll();TreeNode left1 node1.left;TreeNode left2 node2.left;TreeNode right1 node1.right;TreeNode right2 node2.right;if(left1 ! null || left2 ! null){if(left1 ! null left2 ! null){TreeNode left new TreeNode(left1.valleft2.val);node.left left;queue.offer(left);queue1.offer(left1);queue2.offer(left2);}else if(left1 ! null){node.left left1;}else if(left2 ! null){node.left left2;}}if (right1 ! null || right2 ! null) {if (right1 ! null right2 ! null) {TreeNode right new TreeNode(right1.val right2.val);node.right right;queue.offer(right);queue1.offer(right1);queue2.offer(right2);} else if (right1 ! null) {node.right right1;} else {node.right right2;}}}return merged;}
