深度优先遍历 DFS
解题思路
从根节点开始同时遍历两个二叉树，并将对应的节点进行合并；
两个二叉树的对应节点可能存在以下三种情况，对于每种情况使用不同的合并方式：
- 如果两个二叉树的对应节点都为空，则合并后的二叉树的对应节点也为空；
- 如果两个二叉树的对应节点只有一个为空，则合并后的二叉树的对应节点为其中的非空节点；
- 如果两个二叉树的对应节点都不为空，则合并后的二叉树的对应节点的值为两个二叉树的对应节点的值之和，此时需要显性合并两个节点；
对一个节点进行合并之后，还要对该节点的左右子树分别进行合并；
复杂度
-
时间复杂度：
O(min(m,n))，其中 m 和 n 分别是两个二叉树的节点个数； -
空间复杂度：
O(min(m,n))，其中 m 和 n 分别是两个二叉树的节点个数；空间复杂度取决于递归调用的层数，递归调用的层数不会超过较小的二叉树的最大高度，最坏情况下，二叉树的高度等于节点数；
代码实现
var mergeTrees = function (root1, root2) {
if (root1 === null) return root2; // 如果 t1 为空，合并之后就应该是 t2
if (root2 === null) return root1; // 如果 t2 为空，合并之后就应该是 t1
// 修改了 t1 的数值
root1.val += root2.val;
// 修改了 t1 的结构
root1.left = mergeTrees(root1.left, root2.left);
root1.right = mergeTrees(root1.right, root2.right);
return root1;
};
广度优先遍历 BFS
解题思路
使用层序遍历进行遍历；
将节点放入队列中的时候有以下两种情况：
- 如果两个二叉树的对应节点只有一个为空，则将节点更新到第一棵树的对应节点上；
- 如果两个二叉树的对应节点都不为空，则将两个节点都放入队列；
迭代完成后，返回第一棵树的根节点即可；
复杂度
-
时间复杂度：
O(min(m,n))，其中 m 和 n 分别是两个二叉树的节点个数； -
空间复杂度：
O(min(m,n))，其中 m 和 n 分别是两个二叉树的节点个数；空间复杂度取决于队列中的元素个数，队列中的元素个数不会超过较小的二叉树的节点数；
代码实现
var mergeTrees = function (root1, root2) {
if (root1 === null) return root2;
if (root2 === null) return root1;
let queue = [root1, root2];
while (queue.length) {
let node1 = queue.shift();
let node2 = queue.shift();;
node1.val += node2.val;
if (node1.left && node2.left) {
queue.push(node1.left);
queue.push(node2.left);
}
if (node1.right && node2.right) {
queue.push(node1.right);
queue.push(node2.right);
}
if (node1.left === null && node2.left) node1.left = node2.left;
if (node1.right === null && node2.right) node1.right = node2.right;
}
return root1;
};
打赏作者
您的打赏是我前进的动力
微信
支付宝
leetcode🧑💻 654. 最大二叉树
上一篇
评论
