C++ Clean Code - Unique Node | Shared Node


  • 8

    Create new Nodes
    I like to create new nodes for newly formed tree in this type of problem, as you are literally creating nested graph otherwise.

    class Solution {
    public:
        TreeNode* mergeTrees(TreeNode* t1, TreeNode* t2) {
            if (!t1 && !t2) {
                return nullptr;
            }
            TreeNode* node = new TreeNode((t1 ? t1->val : 0) + (t2 ? t2->val : 0));
            node->left = mergeTrees((t1 ? t1->left : nullptr), (t2 ? t2->left : nullptr));
            node->right = mergeTrees((t1 ? t1->right : nullptr), (t2 ? t2->right : nullptr));
            return node;
        }
    };
    

    Share Nodes with the nonnull TreeNode
    As @zqfan point out, this problem explicitly tell you to use the NOT null node, there is no need to create new nodes. And the code would also be simpler.

    class Solution {
    public:
        TreeNode* mergeTrees(TreeNode* t1, TreeNode* t2) {
            if (!t1) return t2;
            if (!t2) return t1;
    
            TreeNode* node = new TreeNode(t1->val + t2->val);
            node->left = mergeTrees(t1->left, t2->left);
            node->right = mergeTrees(t1->right, t2->right);
            return node;
        }
    };
    

  • 3
    Z

    using another logic can make it much cleaner

    class Solution {
    public:
        TreeNode* mergeTrees(TreeNode* t1, TreeNode* t2) {
            if ( t1 && t2 ) {
                TreeNode * root = new TreeNode(t1->val + t2->val);
                root->left = mergeTrees(t1->left, t2->left);
                root->right = mergeTrees(t1->right, t2->right);
                return root;
            } else {
                return t1 ? t1 : t2;
            }
        }
    };
    

    note that the problem described as Otherwise, the NOT null node will be used as the node of new tree. which actually might be wrong in real world but we should follow it in our code.

    ADS: my full version of solutions: https://discuss.leetcode.com/topic/92147/short-recursive-solution-w-python-c


  • 0

    @zqfan Thank you for point out. Updated with another solution.


  • 2
    Q

    @alexander @zqfan A question about the share nodes: if you don't create new node, there are two trees point to the same node. Who should release the memory?


  • 0
    Z

    @qxl052000 said in C++ Clean Code:

    @alexander @zqfan A question about the share nodes: if you don't create new node, there are two trees point to the same node. Who should release the memory?

    in real case we should avoid ambiguous responsibility, with the data structure defined in this problem, I think there is no proper way to free the share nodes. alexander's solution will be your choice in such case.

    I think the meaning of the problem might be let you merge two trees into a new one, abandon the origin two old trees. which means we should free overlapped nodes in t1 and t2 (or reuse t1 instead of create new one), reuse non-overlapped nodes. I could be wrong, but it doesn't matter in contest. you can make it clear during an interview.


  • 0
    9

    @alexander In fact ,There are some new nodes created using new operator and some original nodes form two original trees, if there any ways to avoid the mixture of two different nods?Thanks


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.