题目描述
给定两个二叉树，想象当你将它们中的一个覆盖到另一个上时，两个二叉树的一些节点便会重叠。
你需要将他们合并为一个新的二叉树。合并的规则是如果两个节点重叠，那么将他们的值相加作为节点合并后的新值，否则不为 NULL 的节点将直接作为新二叉树的节点。
示例 1:
输入:
Tree 1 Tree 2
1 2
/ \ / \
3 2 1 3
/ \ \
5 4 7
输出:
合并后的树:
3
/
4 5
/ \ \
5 4 7
注意: 合并必须从两个树的根节点开始。
解题思路
同时遍历二叉树即可
个人解题代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
| class TreeNode {
var val: Int
var left: TreeNode?
var right: TreeNode?
init(_ val: Int) {
self.val = val
self.left = nil
self.right = nil
}
}
class Solution {
func mergeTrees(_ t1: TreeNode?, _ t2: TreeNode?) -> TreeNode? {
var node: TreeNode?
if let tree1 = t1, let tree2 = t2 {
node = TreeNode(tree1.val + tree2.val)
} else if t1 != nil && t2 == nil {
node = TreeNode(t1!.val)
} else if t2 != nil && t1 == nil {
node = TreeNode(t2!.val)
} else {
return nil
}
node?.left = mergeTrees(t1?.left, t2?.left)
node?.right = mergeTrees(t1?.right, t2?.right)
return node
}
}
|
优化代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| class Solution {
func mergeTrees(_ t1: TreeNode?, _ t2: TreeNode?) -> TreeNode? {
guard let tree1 = t1 else { return t2 }
guard let tree2 = t2 else { return t1 }
let node = TreeNode(tree1.val + tree2.val)
node.left = mergeTrees(tree1.left, tree2.left)
node.right = mergeTrees(tree1.right, tree2.right)
return node
}
}
|
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/merge-two-binary-trees