Powered By GitBook
617.Merge Two Binary Trees

617.Merge Two Binary Trees

难度:Easy
给定两个二叉树,想象当你将它们中的一个覆盖到另一个上时,两个二叉树的一些节点便会重叠。 你需要将他们合并为一个新的二叉树。合并的规则是如果两个节点重叠,那么将他们的值相加作为节点合并后的新值,否则不为 NULL 的节点将直接作为新二叉树的节点。
1
示例 1:
2
3
输入:
4
Tree 1 Tree 2
5
1 2
6
/ \ / \
7
3 2 1 3
8
/ \ \
9
5 4 7
10
输出:
11
合并后的树:
12
3
13
/ \
14
4 5
15
/ \ \
16
5 4 7
17
注意: 合并必须从两个树的根节点开始。
Copied!
方法,直接递归。
1
/**
2
* Definition for a binary tree node.
3
* struct TreeNode {
4
* int val;
5
* TreeNode *left;
6
* TreeNode *right;
7
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
8
* };
9
*/
10
class Solution {
11
public:
12
TreeNode* mergeTrees(TreeNode* t1, TreeNode* t2) {
13
14
if(!t1) return t2;
15
if(!t2) return t1;
16
TreeNode* root=t1;
17
root->val +=t2->val;
18
root->left=mergeTrees(t1->left,t2->left);
19
root->right=mergeTrees(t1->right,t2->right);
20
return root;
21
22
}
23
};
Copied!
Last modified 2yr ago
Copy link