Slow but correct verson using DFS, but i can't think a faster one


  • 1
    C
    /**
     * Definition for a binary tree node.
     * struct TreeNode {
     *     int val;
     *     TreeNode *left;
     *     TreeNode *right;
     *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
     * };
     */
    class Solution {
    public:
        // find the pathes to the two nodes using dfs,
        // then find the last common node along the pathes
        
        stack<TreeNode*> path_p;
        stack<TreeNode*> path_q;
        
        bool is_p_found;
        bool is_q_found;
        
        stack<TreeNode*> path;
        
        void reverse_stack(stack<TreeNode*> from, stack<TreeNode*> &to)
        {
            while( !from.empty() )
            {
                to.push( from.top() );
                from.pop();
            }
        }
        
        void dfs(TreeNode *root, const TreeNode *p, const TreeNode *q)
        {
            if(is_p_found && is_q_found) return;
            
            if(!root) return;
            
            path.push(root);
           
            if(root == p)
            {
                reverse_stack(path, path_p);
                is_p_found = true;
            }
            if(root == q)
            {
                reverse_stack(path, path_q);
                is_q_found = true;
            }
            
            dfs(root->left, p, q);
            dfs(root->right, p, q);
            
            path.pop();
        }
        
        TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) 
        {
            if(!p) return q;
            if(!q) return p;
            
            is_p_found = false;
            is_q_found = false;
            
            dfs(root, p, q);
            
            TreeNode *last_common = root;
            while(!path_p.empty() && !path_q.empty())
            {
                if(path_p.top() != path_q.top())
                    return last_common;
                    
                last_common = path_p.top();
                
                path_p.pop();
                path_q.pop();
            }
            
            return last_common;
        }
    };

Log in to reply
 

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