LeetCode #617 "Merge Two Binary Trees" 使用 C++

Question

问题是：

给定两棵二叉树，想象一下，当您将其中一棵树覆盖在另一棵树上时，两棵树的某些节点重叠而其他节点不重叠。

你需要将它们合并成一个新的二叉树。合并规则是，如果两个节点重叠，则将节点值相加作为合并节点的新值。否则，NOT null节点将被用作新树的节点。

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

注意：合并过程必须从两棵树的根节点开始。

我尝试解决这个 leetcode 问题，但总是得到错误的答案。

我的回答是：

**Merged tree:
         3
        / \
       4   5
      /   
     5**

看来我丢了节点4和7。

但是，从std::cout开始，所有的节点都创建了，但是树似乎还没有构建。

非常感谢您对我的代码提出任何意见：

class Solution {

public:

TreeNode* mergeTrees(TreeNode* t1, TreeNode* t2) {
if (t1 == NULL && t2 == NULL)
    return NULL;
else if (t1 == NULL && t2 != NULL) {

    t1 = new TreeNode(t2->val);
    cout << "vq1:" << t1->val << endl;

    mergeTrees(t1->left, t2->left);
    mergeTrees(t1->right, t2->right);
}
else if (t1 != NULL && t2 == NULL) {
    t1->val += 0;
    cout << "vu1:" << t1->val << endl;
    mergeTrees(t1->left, NULL);
    mergeTrees(t1->right, NULL);
}
else if (t1 != NULL && t2 != NULL) {
    t1->val += t2->val;
    cout << "vx1:" << t1->val << endl;

    mergeTrees(t1->left, t2->left);
    mergeTrees(t1->right, t2->right);

}
return t1;
}
};

Answer 1

您更新的是节点而不是节点的左右子节点试试这个，

TreeNode* mergeTrees(TreeNode* t1, TreeNode* t2) {

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

        t1 = new TreeNode(t2->val);
        cout << "vq1:" << t1->val << endl;

        t1->left = mergeTrees(t1->left, t2->left);
        t1->right = mergeTrees(t1->right, t2->right);
    }
    else if (t1 != NULL && t2 == NULL) {
        t1->val += 0;
        cout << "vu1:" << t1->val << endl;
        t1->left = mergeTrees(t1->left, NULL);
        t1->right = mergeTrees(t1->right, NULL);
    }
    else if (t1 != NULL && t2 != NULL) {
        t1->val += t2->val;
        cout << "vx1:" << t1->val << endl;

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

    }
    return t1;
}

LeetCode #617 "Merge Two Binary Trees" 使用 C++

LeetCode #617 "Merge Two Binary Trees" using C++

c++

algorithm

tree

depth-first-search