C++ post-order traversal solution


  • 0
    E
    class Solution {
    public:
        TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
            TreeNode* ancestor = root;
            TreeNode* cur = root;
            // the boolean value denotes whether the right subtree of the node has been traversed
            stack<pair<TreeNode*,bool>> s;
            bool pFound = false, qFound = false;
            while( (!s.empty() || cur) && !(pFound && qFound) ) {
                if(cur) {
                    if(cur == p) {
                        pFound = true;
                        if(qFound) return ancestor;
                        ancestor = cur;
                    }
                    if(cur == q) {
                        qFound = true;
                        if(pFound) return ancestor;
                        ancestor = cur;
                    }
                    s.push(make_pair(cur, false));
                    cur = cur->left;
                } else {
                    pair<TreeNode*, bool> prev = s.top();
                    if(prev.second) {
                        // The right subtree has been traversed
                        s.pop();
                        // Move up ancestor
                        if(prev.first == ancestor && !s.empty()) ancestor = s.top().first;
                    } else {
                        cur = prev.first->right;
                        s.top().second = true;
                    }
                }
            }
            if(pFound && qFound) return ancestor;
            else return NULL;
        }
    };

Log in to reply
 

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