[LintCode] Lowest Common Ancestor

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.

Example

        4

    /     \

  3         7

          /     \

        5         6

For 3 and 5, the LCA is 4.

For 5 and 6, the LCA is 7.

For 6 and 7, the LCA is 7.

Method 1: Transform it to the problem of finding the first common node of two linked lists.

/**
 * Definition of TreeNode:
 * class TreeNode {
 * public:
 *     int val;
 *     TreeNode *left, *right;
 *     TreeNode(int val) {
 *         this->val = val;
 *         this->left = this->right = NULL;
 *     }
 * }
 */
class Solution {
public:
    bool hasNode(vector<TreeNode*> &rec,TreeNode *node, TreeNode *target)
    {
        if(!node) return false;

        if(node == target ||
           hasNode(rec, node->left, target) ||
           hasNode(rec, node->right, target)) 
        {
            rec.push_back(node);
            return true;
        }
        return false;
    }
    TreeNode *lowestCommonAncestor(TreeNode *root, TreeNode *A, TreeNode *B) {
        if(!root) return NULL;
        vector<TreeNode*> recA;
        hasNode(recA, root, A);
        vector<TreeNode*> recB;
        hasNode(recB, root, B);
        
        int lenA = recA.size(), lenB = recB.size();
        if(0 == lenA || 0 == lenB) return NULL;
        int i = lenA-1, j = lenB-1;
        while(i>=0 && j>=0 && recA[i] == recB[j])
        {
            i--;
            j--;
        }
        return recA[i+1];
    }
};

Method 2: Very neat

class Solution {
public:
    TreeNode *lowestCommonAncestor(TreeNode *root, TreeNode *A, TreeNode *B) {
        if(!root) return NULL;
        if(root == A || root == B) return root;
        TreeNode *left = lowestCommonAncestor(root->left, A, B);
        TreeNode *right = lowestCommonAncestor(root->right, A, B);
        if(left && right) return root;
        return left?left:right;
    }
};