题目描述 LeetCode 617

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:

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.

中文描述

给定两棵二叉树，然后对应的节点数值相加，然后形成一课新的树返回。

解题思路

思路1: 对两棵树依次递归，取出两棵树的数值，依次将新的节点加入新的树。
思路2：不建立新的树，在树 t1 的基础的上，将树 t2 的节点值加上 t1 的节点值，然后重新放入 t1，最终 t1 即为两棵树合并成的新树。

C语言代码 -> 思路1

# include <stdio.h>
# include <stdlib.h>

struct TreeNode
{
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
};

// 先序遍历建树
struct TreeNode *create(struct TreeNode *tree)
{
    int ch;

    scanf("%d", &ch);
    
    if(ch == 0)
    {
        tree = NULL;
    }
    else
    {
        tree = (struct TreeNode *)calloc(1, sizeof(struct TreeNode));
        tree -> val = ch;
        tree -> left  = create(tree -> left);
        tree -> right = create(tree -> right);
    }

    return tree;
}

// 先序遍历输出树
void printorder(struct TreeNode *tree)
{
    if(tree)
    {
        printf("%d ", tree -> val);
        printorder(tree -> left);
        printorder(tree -> right);
    }
}

// 从 t1 和 t2 中取出节点数值，从新创建一颗新树
struct TreeNode* mergeTrees(struct TreeNode* t1, struct TreeNode* t2) 
{
    struct TreeNode *tree = NULL;
    int val = 0;
    
    if(t1 != NULL || t2 != NULL)
    {
        tree = (struct TreeNode *)calloc(1, sizeof(struct TreeNode));

        if( t1 != NULL && t2 != NULL)
        {
            val = t1 -> val + t2 -> val;
            tree -> val = val;
            tree -> left  = mergeTrees(t1 -> left, t2 -> left);
            tree -> right = mergeTrees(t1 -> right, t2 -> right); 
        }
        else if(t1 != NULL && t2 == NULL)
        {
            val = t1 -> val;
            tree -> val = val;
            tree -> left  = mergeTrees(t1 -> left, NULL);
            tree -> right = mergeTrees(t1 -> right, NULL); 
        }
        else if(t1 == NULL && t2 != NULL)
        {
            val = t2 -> val;
            tree -> val = val;
            tree -> left  = mergeTrees(NULL, t2 -> left);
            tree -> right = mergeTrees(NULL, t2 -> right); 
        }

        return tree;
    }
    else
    {
        return NULL;
    }

}

main()
{
    struct TreeNode *t1 = NULL;
    struct TreeNode *t2 = NULL;
    struct TreeNode *tree = NULL;
    
    t1 = create(t1);
    t2 = create(t2);
    
    tree = mergeTrees(t1, t2);
    printorder(tree);
    printf("\n\n");
    /*
    printf("xianxu ->> ");
    printorder(t1);
    printf("\n\n");
    printorder(t2);
    printf("\n");*/
}

验证代码

运行结果

C语言代码 -> 思路2

# include <stdio.h>
# include <stdlib.h>

struct TreeNode
{
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
};

// 先序遍历创建树
struct TreeNode *create(struct TreeNode *tree)
{
    int ch;

    scanf("%d", &ch);
    
    if(ch == 0)
    {
        tree = NULL;
    }
    else
    {
        tree = (struct TreeNode *)calloc(1, sizeof(struct TreeNode));
        tree -> val = ch;
        tree -> left  = create(tree -> left);
        tree -> right = create(tree -> right);
    }

    return tree;
}

// 先序遍历输出树
void printorder(struct TreeNode *tree)
{
    if(tree)
    {
        printf("%d ", tree -> val);
        printorder(tree -> left);
        printorder(tree -> right);
    }
}

// 将树 t2 的内容合并到 t1 上面
struct TreeNode* mergeTrees(struct TreeNode* t1, struct TreeNode* t2) 
{
    if(t1 != NULL || t2 != NULL)
    {
        if( t1 != NULL && t2 != NULL)
        {
            t1 -> val = t1 -> val + t2 -> val;
            t1 -> left  = mergeTrees(t1 -> left, t2 -> left);
            t1 -> right = mergeTrees(t1 -> right, t2 -> right); 

            return t1;
        }
        else if(t1 != NULL && t2 == NULL)
        {
            return t1;
        }
        else  //(t1 == NULL && t2 != NULL)
        {
            return t2;
        }
    }
    else
    {
        return NULL;
    }
}

main()
{
    struct TreeNode *t1 = NULL;
    struct TreeNode *t2 = NULL;
    
    t1 = create(t1);
    t2 = create(t2);
    
    t1 = mergeTrees(t1, t2);
    printorder(t1);
    printf("\n\n");
}

验证代码

运行结果

思路2 代码精简版

看着谈论区里面的解答，优秀和思路2 类似，但是我的判断有点多，所以精简一下，但是大体实现思路是一致的，不可思议的是，精简之后的 runtime 还是和前两个 runtime 一模一样，真是费解！！！

/**
 * 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 == NULL)
    {
        return t2;
    }
    else if(t2 == NULL)
    {
        return t1;
    }
    
    t1 -> val = t1 -> val + t2 -> val;
    t1 -> left  = mergeTrees(t1 -> left, t2 -> left);
    t1 -> right = mergeTrees(t1 -> right, t2 -> right); 

    return t1;
}

运行结果

思考

• 两种思路按理说 思路2 的 runtime 应该小的，毕竟没有创建新的树嘛，，但是两个思路代码竟然时间一样，都是 20ms，，真是，，不得其所！！！