TREE——617. Merge Two Binary Tree

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:

图片.png

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

题意

将两个树合并，对应的位置进行加法运算，如果都不存在就为空

思路

递归思想。首先判断要合并的两个树是否都为空，如果都为空就返回NULL，否则说明合并后这个节点存在，新建一个树，求它的val有一点技巧，即如果有一颗树为空就加0。最后再分别对其左子树右子树做相同操作即可。

代码

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
struct TreeNode* mergeTrees(struct TreeNode* t1, struct TreeNode* t2) {
    if(!t1&&!t2)
        return NULL;
    struct TreeNode *result=malloc(sizeof(struct TreeNode));
    result->val=(t1?t1->val:0)+(t2?t2->val:0);
    result->left=mergeTrees(t1?t1->left:NULL,t2?t2->left:NULL);
    result->right=mergeTrees(t1?t1->right:NULL,t2?t2->right:NULL);
    return result;
}