TOP101题解 | BM32#合并二叉树#

/**
 * struct TreeNode {
 *	int val;
 *	struct TreeNode *left;
 *	struct TreeNode *right;
 * };
 */
/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 * @author Senky
 * @date 2023.08.01
 * @par url https://www.nowcoder.com/creation/manager/content/584337070?type=column&status=-1
 * @brief 
 * 时间复杂度O(n)空间复杂度O(n) :
 *      如果两颗树的当前节点均存在，那么将它们的值相加，并递归合并左子树和右子树。
 *      如果一颗树的节点为空，而另一颗树的节点不为空，那么将非空树的节点作为合并后树的节点。
 *      如果两颗树的节点均为空，那么直接返回空节点。
 * 时间复杂度O(n)空间复杂度O(1) :
 *      在这个问题中，我们可以将其中一棵树作为参照，然后将另一棵树上缺少的节点添加到参照树上，而不需要创建新的节点。
 *      如果参照树节点不为空，而另一棵树节点为空，则将参照树节点保留不变，因为它是合并后的结果。
 *      如果参照树节点为空，而另一棵树节点不为空，则将参照树节点用另一棵树节点替换，因为它是合并后的结果。
 *      如果参照树节点和另一棵树节点均不为空，则将它们的值相加，并递归合并它们的左子树和右子树。
 * @param t1 TreeNode类 
 * @param t2 TreeNode类 
 * @return TreeNode类
 */
#include <stdlib.h>
struct TreeNode* mergeTrees(struct TreeNode* t1, struct TreeNode* t2 ) {
    // write code here
    if(NULL == t1)
    {
        return t2;
    }

    if(NULL ==t2)
    {
        return t1;
    }

    //由于这里会递归调用，而且生成的结点自动会将数据域和左右指针域赋正确的值
    struct TreeNode* MergeTree = (struct TreeNode*)malloc(sizeof(struct TreeNode));

    MergeTree->val = t1->val + t2->val;
    MergeTree->left = mergeTrees(t1->left, t2->left);
    MergeTree->right = mergeTrees(t1->right, t2->right);

    return MergeTree;
}

/**
 * struct TreeNode {
 *	int val;
 *	struct TreeNode *left;
 *	struct TreeNode *right;
 * };
 */
/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 * @author Senky
 * @date 2023.08.01
 * @par url https://www.nowcoder.com/creation/manager/content/584337070?type=column&status=-1
 * @brief 
 * 时间复杂度O(n)空间复杂度O(n) :
 *      如果两颗树的当前节点均存在，那么将它们的值相加，并递归合并左子树和右子树。
 *      如果一颗树的节点为空，而另一颗树的节点不为空，那么将非空树的节点作为合并后树的节点。
 *      如果两颗树的节点均为空，那么直接返回空节点。
 * 时间复杂度O(n)空间复杂度O(1) :
 *      在这个问题中，我们可以将其中一棵树作为参照，然后将另一棵树上缺少的节点添加到参照树上，而不需要创建新的节点。
 *      如果参照树节点不为空，而另一棵树节点为空，则将参照树节点保留不变，因为它是合并后的结果。
 *      如果参照树节点为空，而另一棵树节点不为空，则将参照树节点用另一棵树节点替换，因为它是合并后的结果。
 *      如果参照树节点和另一棵树节点均不为空，则将它们的值相加，并递归合并它们的左子树和右子树。
 * @param t1 TreeNode类 
 * @param t2 TreeNode类 
 * @return TreeNode类
 */
#include <stdlib.h>
struct TreeNode* mergeTrees(struct TreeNode* t1, struct TreeNode* t2) {
    if (t1 == NULL) {
        return t2;
    }
    if (t2 == NULL) {
        return t1;
    }

    t1->val += t2->val;
    t1->left = mergeTrees(t1->left, t2->left);
    t1->right = mergeTrees(t1->right, t2->right);

    return t1;
}