# Lowest Common Ancestor

## Question

### Problem Statement

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

For the following binary tree:

  4
/ \
3   7
/ \
5   6


LCA(3, 5) = 4

LCA(5, 6) = 7

LCA(6, 7) = 7

## 题解1 - 自底向上

1. 当前节点不是两个节点中的任意一个，此时应判断左右子树的返回结果。
• 若左右子树均返回非空节点，那么当前节点一定是所求的根节点，将当前节点逐层向前汇报。// 两个节点分居树的两侧
• 若左右子树仅有一个子树返回非空节点，则将此非空节点向父节点汇报。// 节点仅存在于树的一侧
• 若左右子树均返回NULL, 则向父节点返回NULL. // 节点不在这棵树中
2. 当前节点即为两个节点中的一个，此时向父节点返回当前节点。

### C++ Recursion From Bottom to Top

/**
* 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:
/**
* @param root: The root of the binary search tree.
* @param A and B: two nodes in a Binary.
* @return: Return the least common ancestor(LCA) of the two nodes.
*/
TreeNode *lowestCommonAncestor(TreeNode *root, TreeNode *A, TreeNode *B) {
// return either A or B or NULL
if (NULL == root || root == A || root == B) return root;

TreeNode *left = lowestCommonAncestor(root->left, A, B);
TreeNode *right = lowestCommonAncestor(root->right, A, B);

// A and B are on both sides
if ((NULL != left) && (NULL != right)) return root;

// either left or right or NULL
return (NULL != left) ? left : right;
}
};


### Java

/**
* Definition of TreeNode:
* public class TreeNode {
*     public int val;
*     public TreeNode left, right;
*     public TreeNode(int val) {
*         this.val = val;
*         this.left = this.right = null;
*     }
* }
*/
public class Solution {
/**
* @param root: The root of the binary search tree.
* @param A and B: two nodes in a Binary.
* @return: Return the least common ancestor(LCA) of the two nodes.
*/
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode A, TreeNode B) {
if (root == null) return null;

TreeNode lNode = lowestCommonAncestor(root.left, A, B);
TreeNode rNode = lowestCommonAncestor(root.right, A, B);
// root is the LCA of A and B
if (lNode != null && rNode != null) return root;
// root node is A/B(including the case below)
if (root == A || root == B) return root;
// return lNode/rNode if root is not LCA
return (lNode != null) ? lNode : rNode;
}
}


### 源码分析

fixme 细心的你也许会发现，其实题解的分析漏掉了一种情况，即树中可能只含有 A/B 中的一个节点！这种情况应该返回空值，但上述实现均返回非空节点。

## 题解 - 自底向上(计数器)

### C++

/**
* 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:
/**
* @param root: The root of the binary search tree.
* @param A and B: two nodes in a Binary.
* @return: Return the least common ancestor(LCA) of the two nodes.
*/
TreeNode *lowestCommonAncestor(TreeNode *root, TreeNode *A, TreeNode *B) {
if ((NULL == A) || (NULL == B)) return NULL;

pair<TreeNode *, int> result = helper(root, A, B);

if (A != B) {
return (2 == result.second) ? result.first : NULL;
} else {
return (1 == result.second) ? result.first : NULL;
}
}

private:
pair<TreeNode *, int> helper(TreeNode *root, TreeNode *A, TreeNode *B) {
TreeNode * node = NULL;
if (NULL == root) return make_pair(node, 0);

pair<TreeNode *, int> left = helper(root->left, A, B);
pair<TreeNode *, int> right = helper(root->right, A, B);

// return either A or B
int count = max(left.second, right.second);
if (A == root || B == root)  return make_pair(root, ++count);

// A and B are on both sides
if (NULL != left.first && NULL != right.first) return make_pair(root, 2);

// return either left or right or NULL
return (NULL != left.first) ? left : right;
}
};


### Java

/**
* Definition of TreeNode:
* public class TreeNode {
*     public int val;
*     public TreeNode left, right;
*     public TreeNode(int val) {
*         this.val = val;
*         this.left = this.right = null;
*     }
* }
*/
public class Solution {
private int count = 0;
/**
* @param root: The root of the binary search tree.
* @param A and B: two nodes in a Binary.
* @return: Return the least common ancestor(LCA) of the two nodes.
*/
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode A, TreeNode B) {
TreeNode result = helper(root, A, B);
if (A == B) {
return result;
} else {
return (count == 2) ? result : null;
}
}

private TreeNode helper(TreeNode root, TreeNode A, TreeNode B) {
if (root == null) return null;

TreeNode lNode = helper(root.left, A, B);
TreeNode rNode = helper(root.right, A, B);
// root is the LCA of A and B
if (lNode != null && rNode != null) return root;
// root node is A/B(including the case below)
if (root == A || root == B) {
count++;
return root;
}
// return lNode/rNode if root is not LCA
return (lNode != null) ? lNode : rNode;
}
}


### 源码分析

A == B时，计数器返回1的节点即为我们需要的节点，否则只取返回2的节点，如此便保证了该方法的正确性。对这种实现还有问题的在下面评论吧。