Lowest Common Ancestor II (Ladder)

Description

Given the root and two nodes in a Binary Tree. Find the lowest common ancestor(LCA) of the two nodes.

The lowest common ancestor is the node with largest depth which is the ancestor of both nodes.

The node has an extra attribute parent which point to the father of itself. The root's parent is null.

Example:
For the following binary tree:

  4
 / \
3   7
   / \
  5   6

LCA(3, 5) = 4
LCA(5, 6) = 7
LCA(6, 7) = 7

Link

Lintcode_ladder

Method

1. Get all path, then from root to leaf nodes, finding the final common nodes
2. Go from nodes to the root. When reaching the root, we start over from another node. Until this two meets, we get the LCA.

Example

1. 1

   /**
   * Definition of ParentTreeNode:
   * class ParentTreeNode {
   * public:
   *     int val;
   *     ParentTreeNode *parent, *left, *right;
   * }
   */
   class Solution {
   public:
    /**
     * @param root: The root of the tree
     * @param A, B: Two node in the tree
     * @return: The lowest common ancestor of A and B
     */
    // -------------------------------------------------------------------
    // // Version 1, 
    // // Find path to the root,
    // // Then, compare from root -> node, find max common length
    ParentTreeNode *lowestCommonAncestorII(ParentTreeNode *root,
                                          ParentTreeNode *A,
                                          ParentTreeNode *B) {
        // Write your code here
        if (!root) {
            return nullptr;
        }
        vector<ParentTreeNode*> pathA;
        vector<ParentTreeNode*> pathB;
        // find the path from A to root, record itself at first
        while (A->parent) {
            pathA.push_back(A);
            A = A->parent;
        }
        // find the path from B to root, record itself at first
        while (B->parent) {
            pathB.push_back(B);
            B = B->parent;
        }
        // from back to begin, search the last common node
        int aback = pathA.size() - 1;
        int bback = pathB.size() - 1;
        ParentTreeNode* result = root;
        while (aback >= 0 && bback >= 0) {
            if (pathA[aback] == pathB[bback]) {
                result = pathA[aback];
            }
            --aback;
            --bback;
        }
        return result;
    }
    // -------------------------------------------------------------------
    // Version 2,
    // From two node go to root,
    // if one reaches the root, then using another node reaches root again
    //  until they meet in one node
    ParentTreeNode *lowestCommonAncestorII(ParentTreeNode *root,
                                           ParentTreeNode *A,
                                           ParentTreeNode *B) {
        if (!root) {
            return nullptr;
        }
        // make sure that A shallow then B deep
        int depthA = depth(A);
        int depthB = depth(B);
        if (depthA > depthB) {
            swap(depthA, depthB);
            swap(A, B);
        }
        ParentTreeNode* Astart = A;
        ParentTreeNode* Bstart = B;
        // search for LCA
        while (A) {
            A = A->parent;
            B = B->parent;
        }
        A = Bstart;
        while (B) {
            A = A->parent;
            B = B->parent;
        }
        B = Astart;
        while (A && B) {
            if (A == B) {
                return A;
            }
            A = A->parent;
            B = B->parent;
        }
        return root;
    }
    int depth(ParentTreeNode* head) {
        if (!head) {
            return 0;
        }
        int result = 0;
        while (head->parent) {
            ++result;
            head = head->parent;
        }
        return result;
    }
   };
   

Similar problems

x

Tags

x