C++_O(h)_Inorder Traverse_Accepted_36ms_52.20%


  • 0

    Key: Use an indicator to record whether the TreeNode* p has appeared in last loop.

    class Solution {
    public:
    TreeNode* inorderSuccessor(TreeNode* root, TreeNode* p) {
        stack<TreeNode*> s;
        int i = 0;
        while(true){
            toTheLeft(root, s);
            if(s.empty()) break;
            root = s.top();
            if(i == 1){return root;}
            else if(root == p){i = 1;}
            s.pop();
            root = root->right;
        }
        return nullptr;
    }
    
    void toTheLeft(TreeNode* root, stack<TreeNode*>& s){
        while(root){
            s.push(root);
            root = root->left;
        }
    }
    };
    

    0_1476397435827_屏幕快照 2016-10-13 下午6.21.49.png


Log in to reply
 

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