合并二叉树
LeetCode617. 合并二叉树
给你两棵二叉树：root1和root2。
想象一下，当你将其中一棵覆盖到另一棵之上时，两棵树上的一些节点将会重叠（而另一些不会）。你需要将这两棵树合并成一棵新二叉树。合并的规则是：如果两个节点重叠，那么将这两个节点的值相加作为合并后节点的新值；否则，不为null的节点将直接作为新二叉树的节点。
返回合并后的二叉树。
注意: 合并过程必须从两个树的根节点开始。
- 确定递归函数的参数和返回值
- 参数：传入两个二叉树的根节点
- 返回值：合并后的二叉树的根节点
- 确定终止条件
- 确定单层递归的逻辑
代码
Go
1
2
3
4
5
6
7
8
9
10
11
12
13
14
|
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
}
|
Link
GitHub