Long but easy to understand

  • 0

    Here is prose instead of poetry...

        //helper function to extract path to a node
        void pathtonode(TreeNode* root, TreeNode* p, std::vector<TreeNode*>& path)
             TreeNode* cur = root;
             while (cur)
                 if (cur==p) break;
                 cur = (p->val > cur->val) ? cur->right : cur->left;
        TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
            //get path to the nodes
            std::vector<TreeNode*> pathp, pathq;
            pathtonode(root, p, pathp);
            pathtonode(root, q, pathq);
            //now extract common path
            int maxsize = min(pathp.size(), pathq.size());
            int i=0;
            for ( ; i<maxsize; i++)
              if (pathp[i]!=pathq[i]) break;
            return pathp[i-1]; 

Log in to reply

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