My C++ solution using O(n) time


  • 1
    M
    bool Traverse(TreeNode * root, TreeNode *p, stack<TreeNode *> & list1)
    {
        if(root == NULL)
            return false;
        if(root == p)
        {
            list1.push(root);
            return true;
        }
        else
        {
            if( Traverse(root->left, p,list1))
           {
               list1.push(root);
               return true;
           }
           else if(Traverse(root->right, p, list1))
            {
                list1.push(root);
                return true;
            }
            else
            {
                return false;
            }
        }
    }
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        stack<TreeNode *> list1;
        stack<TreeNode *> list2;
        Traverse(root, p, list1);
        Traverse(root, q, list2);
        TreeNode * pbackup = NULL;
        while(!list1.empty() && !list2.empty())
        {
            if(list1.top() == list2.top())
            {
                pbackup = list1.top();
                list1.pop();
                list2.pop();
            }
            else
                break;
        }
        return pbackup;
    }

Log in to reply
 

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