C++ Iterative Solution


  • 0
    Y

    Using a stack of pair<TreeNode*, TreeNode*> to access nodes in both trees.

    class Solution {
    public:
        TreeNode* mergeTrees(TreeNode* t1, TreeNode* t2) {
            
            if (t1 == NULL) {
                return t2;
            }
            stack<pair<TreeNode*, TreeNode*>> s;
            s.push(make_pair(t1, t2));
            while (!s.empty()) {
                pair<TreeNode*, TreeNode*> curr = s.top();
                s.pop();
                if (curr.first == NULL || curr.second == NULL) continue;
                curr.first->val += curr.second->val;
                if (curr.first->left == NULL) {
                    curr.first->left = curr.second->left;
                }
                else {
                    s.push(make_pair(curr.first->left, curr.second->left));
                }
                if (curr.first->right == NULL) {
                    curr.first->right = curr.second->right;
                }
                else {
                    s.push(make_pair(curr.first->right, curr.second->right));
                }
            }
            return t1;
            
        }
    };
    

Log in to reply
 

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