【一天一大 lee】 合并二叉树 (难度:简单)-Day20200923
【一天一大 lee】 合并二叉树 (难度:简单)-Day20200923
前端小书童
发布于 2020-09-29 20:23:01
发布于 2020-09-29 20:23:01
代码可运行
运行总次数：0
代码可运行
题目:[1]
给定两个二叉树，想象当你将它们中的一个覆盖到另一个上时，两个二叉树的一些节点便会重叠。
你需要将他们合并为一个新的二叉树。合并的规则是如果两个节点重叠，那么将他们的值相加作为节点合并后的新值，否则不为 NULL 的节点将直接作为新二叉树的节点。
示例：
- 示例 1：
输入:
Tree 1 Tree 2
1 2
/ \ / \
3 2 1 3
/ \ \
5 4 7
输出:
合并后的树:
3
/ \
4 5
/ \ \
5 4 7注意: 合并必须从两个树的根节点开始。
抛砖引玉
思路
同步遍历两个二叉树，并且将到的节点相加，和作为新二叉树的节点
每次遍历将新的二叉树作为子树追加到上一次生成的的二叉树中
特殊情况
两个二叉树，其中任意一个为 null，直接返回另外一个
深度优先遍历（DFS）
/**
* Definition for a binary tree node.
* function TreeNode(val) {
* this.val = val;
* this.left = this.right = null;
* }
*/
/**
* @param {TreeNode} t1
* @param {TreeNode} t2
* @return {TreeNode}
*/
var mergeTrees = function(t1, t2) {
if (t1 == null) return t2
if (t2 == null) return t1
function dfs(node1, node2) {
if (node1 == null) return node2
if (node2 == null) return node1
let node = new TreeNode(node1.val + node2.val)
// 追加二叉左子树
node.left = dfs(node1.left, node2.left)
// 追加二叉右子树
node.right = dfs(node1.right, node2.right)
return node
}
return dfs(t1, t2)
}优化
给定的二叉树，后续不再适用，那么可以将任意取两个二叉树中的一个，在其上累计另外一个二叉树，最后返回那个二叉树，这样省略了每层生成新树的逻辑
var mergeTrees = function(t1, t2) {
if (t1 == null) return t2
if (t2 == null) return t1
function dfs(node1, node2) {
if (node1 == null) return node2
if (node2 == null) return node1
node1.val += node2.val
node1.left = dfs(node1.left, node2.left)
node1.right = dfs(node1.right, node2.right)
return node1
}
return dfs(t1, t2)
}广度优先遍历（BFS）
二叉树的遍历除了 DFS 还可以使用 BFS：
- 按照未优化之前的逻辑，那么需要上个数组来记录遍历中需要除了的元素
具体遍历逻辑与二叉树一遍 BFS 遍历一样：将待处理节点推送到数组，再依次取出，取出处理时将下一次再次推送到待处理数组。
注意
- 注意推送待处理元素时，防止错误需要都推送
- 两个二叉树如果其中一个节点为 null，则新树可以直接使用另外一个二叉树的节点
- queue 新树待拼接节点
- queue1，t1 待遍历节点
- queue2，t2 待遍历节点
var mergeTrees = function(t1, t2) {
if (t1 == null) return t2
if (t2 == null) return t1
let root = new TreeNode(t1.val + t2.val),
queue = [root],
queue1 = [t1],
queue2 = [t2]
while (queue1.length && queue2.length) {
let node = queue.shift(),
node1 = queue1.shift(),
node2 = queue2.shift(),
left1 = node1.left,
left2 = node2.left,
right1 = node1.right,
right2 = node2.right
if (left1 != null || left2 != null) {
if (left1 != null && left2 != null) {
let left = new TreeNode(left1.val + left2.val)
// 注意推送待处理元素时，防止错误需要都推送
node.left = left
queue.push(left)
queue1.push(left1)
queue2.push(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) {
let right = new TreeNode(right1.val + right2.val)
// 注意推送待处理元素时，防止错误需要都推送
node.right = right
queue.push(right)
queue1.push(right1)
queue2.push(right2)
} else if (right1 != null) {
node.right = right1
} else {
node.right = right2
}
}
}
return root
}优化
参照上面的逻辑，不生产新树，在 t1 中做累计
var mergeTrees = function(t1, t2) {
if (t1 == null) return t2
if (t2 == null) return t1
let queue1 = [t1],
queue2 = [t2]
while (queue1.length && queue2.length) {
let node1 = queue1.shift(),
node2 = queue2.shift(),
left1 = node1.left,
left2 = node2.left,
right1 = node1.right,
right2 = node2.right
node1.val += node2.val
if (left1 != null || left2 != null) {
if (left1 != null && left2 != null) {
queue1.push(left1)
queue2.push(left2)
} else if (left2 != null) {
node1.left = left2
}
}
if (right1 != null || right2 != null) {
if (right1 != null && right2 != null) {
queue1.push(right1)
queue2.push(right2)
} else if (right2 != null) {
node1.right = right2
}
}
}
return t1
}本文参与 腾讯云自媒体同步曝光计划，分享自微信公众号。
原始发表：2020-09-23，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录
腾讯云开发者
