Long but easy to understand


  • 0
    B

    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)
             {
                 path.push_back(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.