617. Merge Two Binary Trees

发表于 | 分类于 | |

Given two binary trees and imagine that when you put one of them to cover the other, some nodes of the two trees are overlapped while the others are not.

You need to merge them into a new binary tree. The merge rule is that if two nodes overlap, then sum node values up as the new value of the merged node. Otherwise, the NOT null node will be used as the node of new tree.

Example 1:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
> > > Input: 
> > > 	Tree 1                     Tree 2                  
> > >           1                         2                             
> > >          / \                       / \                            
> > >         3   2                     1   3                        
> > >        /                           \   \                      
> > >       5                             4   7                  
> > > Output: 
> > > Merged tree:
> > > 	     3
> > > 	    / \
> > > 	   4   5
> > > 	  / \   \ 
> > > 	 5   4   7
> > >
> > >
> >

>

Note: The merging process must start from the root nodes of both trees.

题意是要将两棵旧树进行合并新的一棵树。

合并的规则是这样子的，如果两棵旧树对应的节点上都有值得话，那么合并后得到的新树对应节点的则为两个旧树的对应节点的和，如果两颗旧树有一棵对应节点值为空，那么合并后的新树对应节点值则为有值那棵旧树对应节点的值。

虽然在LeetCode上这是一道easy的题目，但是因为自从保完研后基本就没有看过数据结构了，对于树的结构已经很陌生了。所以自己想了许久却无从下手，大概知道需要用到递归。

最后是在看了大神们的解决方法后，思考和回忆了一会才看懂了解题思路。大题如下：

令两颗旧树分别为t1,t2。

  • 首先处理t1,t2都非空的情况（即t1&&t2为真），新建一个树节点root，节点值为t1,t2对应节点值之和。然后对root的左子树和右子树递归调用合并函数。root的左子树由t1左子树和t2左子树合并而成，同理，root的右子树由t1右子树和t2右子树合并而成，最后返回合并的root节点。
  • 然后处理t1和t2有节点为空（有一个为空或者两者都为空）的情况，如果t1不为空，则返回t1，如果t1为空，则返回t2。即t1?t1:t2
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
// Definition for a binary tree node.
struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

class Solution {
public:
    TreeNode *mergeTrees(TreeNode *t1, TreeNode *t2) {
        //t1,t2都非空
        if (t1 && t2) {
            TreeNode *root = new TreeNode(t1->val + t2->val);
          	//合并生成root的左子树
            root->left = mergeTrees(t1->left, t2->left);
            //合并生成root的右子树
            root->right = mergeTrees(t1->right, t2->right);
            return root;
	
        } else {
            //t1和t2有节点为空
            return t1 ? t1 : t2;
        }
    }
};