More Common Way to Find the LCA of Two Nodes in Binary Tree(No Need to be BST, C 24ms)


  • 0
    S
    bool InOrder(struct TreeNode *root, struct TreeNode *p, struct TreeNode *q, struct TreeNode **lca) {
     if (root == NULL) {
         return false;
     }
     if (root == p) {
         if (q == 0) {
             return true;
         }
         if (InOrder(p, q, 0, 0)) {//if q can be traversed from q by InOrder Traverse
            *lca = p;
            return true;
         } else {
            *lca = 0;
            return true;
         }
     }
     if (q == 0) {
         return (InOrder(root->left, p, 0, 0) || InOrder(root->right, p, 0, 0));
     }
    
     bool in_left = InOrder(root->left, p, q, lca);
     if (in_left == true) {//p resides in left of root
         if (*lca == 0) {//but lca not exist currently
             if (InOrder(root, q, 0, 0)) {//current root is lca
                *lca = root;
                return true;
             } else {
                *lca = 0;
                return true;
             }
         } else {
             return true;
         }
     }
     bool in_right = InOrder(root->right, p, q, lca);
     if (in_right == true) {
         if (*lca == 0) {
             if (InOrder(root, q, 0, 0)) {
                 *lca = root;
                 return true;
             } else {
                 *lca = 0;
                 return true;
             }
         } else {
             return true;
         }
     }
     return false;
    }
    struct TreeNode* lowestCommonAncestor(struct TreeNode* root, struct TreeNode* p, struct TreeNode* q) {
        struct TreeNode *lca = 0;
        InOrder(root, p, q, &lca);
        return lca;
    }

Log in to reply
 

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