给你两棵二叉树: root1
和 root2
。
想象一下,当你将其中一棵覆盖到另一棵之上时,两棵树上的一些节点将会重叠(而另一些不会)。你需要将这两棵树合并成一棵新二叉树。合并的规则是:如果两个节点重叠,那么将这两个节点的值相加作为合并后节点的新值;否则,不为 null 的节点将直接作为新二叉树的节点。
返回合并后的二叉树。
注意: 合并过程必须从两个树的根节点开始。
示例 1:
![](https://github.xin/wp-content/uploads/2023/07/65464c31b2e6ac0-1024x278.jpg)
输入: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
题解:
递归法:
func mergeTrees(root1 *TreeNode, root2 *TreeNode) *TreeNode {
if root1 == nil {
return root2
}
if root2 == nil {
return root1
}
root1.Val += root2.Val
root1.Left = mergeTrees(root1.Left, root2.Left)
root1.Right = mergeTrees(root1.Right, root2.Right)
return root1
}
迭代法(使用了队列):
func mergeTrees(root1 *TreeNode, root2 *TreeNode) *TreeNode {
if root1 == nil {
return root2
}
if root2 == nil {
return root1
}
queue := list.New()
queue.PushBack(root1)
queue.PushBack(root2)
for queue.Len() > 0 {
node1 := queue.Remove(queue.Front()).(*TreeNode)
node2 := queue.Remove(queue.Front()).(*TreeNode)
node1.Val += node2.Val
// 左子树都不为空,将左子树分别压入栈,进行更深一度的遍历
if node1.Left != nil && node2.Left != nil {
queue.PushBack(node1.Left)
queue.PushBack(node2.Left)
}
// 右子树都不为空,将右子树分别压入栈,进行更深一度的遍历
if node1.Right != nil && node2.Right != nil {
queue.PushBack(node1.Right)
queue.PushBack(node2.Right)
}
// 左子树为空,直接将树 2 的左子树给树 1
if node1.Left == nil {
node1.Left = node2.Left
}
// 右子树为空,直接将树 2 的右子树给树 1
if node1.Right == nil {
node1.Right = node2.Right
}
}
return root1
}
评论前必须登录!
注册