C++ iterative Solution


  • 0
    L
    1. First we go all the way on the left to store all 'leftmost' nodes. When finish, the top element is the new root.
    2. Then we do backtrack with the stack. For each time, we find a node and its parent node, then we manipulate them according to the instructions.
    3. Don't forget the fact that for the final stage, we need handle the children of the old root.

    Hope it helps.

    public:
        TreeNode* upsideDownBinaryTree(TreeNode* root) {
            if(!root)   return root;
            stack<TreeNode*> myStack;
            TreeNode* newRoot;
            TreeNode* cur = root;
            
            // push the left children all along to the stack
            while(cur)
            {
                myStack.push(cur);
                cur = cur -> left;
            }
            
            // grep the new root
            newRoot = myStack.top();
            
            // We propose the upsideDown
            TreeNode* curParent;
            while(!myStack.empty())
            {
                cur = myStack.top();
                myStack.pop();
                if(myStack.empty()) break;
                curParent = myStack.top();
                cur -> left = curParent -> right;
                cur -> right = curParent;
            }
            
            // set the children of original root to NULL
            cur -> left = NULL;
            cur -> right = NULL;
            
            return newRoot;
        }
    };

Log in to reply
 

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