C++ using a stack, why this doesn't work?


  • 0
    E
    class Solution {
    public:
        TreeNode *upsideDownBinaryTree(TreeNode *root) {
            stack<TreeNode *> stk;
            if (root == nullptr) return root;
         //like in-order traverse, push all the left nodes to the stack
            while(root != nullptr) {
                stk.push(root);
                root = root->left;
            }
            root = stk.top();    //keep root as the leftmost node in the original tree since the leftmost node will be the root of result tree
        // p is previous node just traversed(lower level in original tree), 
        // q is current node (higher level in original tree).
            while(stk.size() > 1) {
                TreeNode *p = stk.top();
                stk.pop();
                TreeNode *q = stk.top();
                if(q->right != nullptr) {    //if q has no right child
                    p->left = q->right;     
                }
                p->right = q;          //set current node as previous node's right child
            }
            return root;
        }
    };
    

    run time error at the case {1,2}, why?


  • 0
    E

    I found the problem. I forgot to set the some left and/or right child to nullptr.


Log in to reply
 

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