Lowest Common Ancestor
Lowest Common Ancestor (leetcodelindcode)
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.
Notice
Assume two nodes are exist in tree.
Example
For the following binary tree:
4
/ \
3 7
/ \
5 6
LCA(3, 5) = 4
LCA(5, 6) = 7
LCA(6, 7) = 7
解题思路
一、分治法
思路：使用深度优先搜索，从叶子结点开始，标记子树中出现目标结点的情况。如果子树中有目标结点，那么标记该结点，否则标记为null。如果左子树、右子树都有标记，说明已经找到最小公共祖先了。如果在根结点为A的左右子树中寻找A和B的公共祖先，就是结点A本身。
换个角度：如果结点C的左子树有一个目标结点，右子树没有，则该结点非最小公共祖先。如果结点C的右子树有一个目标结点，左子树没有，则该节点亦非最小公共祖先。只有当节点C左子树有一个目标结点，右子树也有一个的时候，才是最小公共祖先。
在二叉树中寻找结点A和B的LCA：
- 如果左右子树都有返回值，说明当前结点就是
LCA，直接返回。 - 如果只找到
A，返回A。 - 如果只找到
B，返回B。 - 如果都没有找到，就返回
null。
算法复杂度
- 时间复杂度：每个结点遍历一遍，每个结点的操作是常数个，所以时间复杂度是
O(n)。 - 空间复杂度：使用了常数个辅助变量保存参数，空间复杂度为
O(1)。
Follow up question
- 如果是二叉搜索树，要怎么做？
- 如果每个结点有父亲指针，要怎么做？
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
|| root == A || root == B) {
return
root;
}
// Divide
TreeNode left = lowestCommonAncestor(root.left, A, B);
TreeNode right = lowestCommonAncestor(root.right, A, B);
// Conquer
// 只有在找到A或B的情况下返回值才不为null，所以以此为条件判断是否找到LCA
if
(left !=
null
&
&
right !=
null
) {
return
root;
}
if
(left !=
null
) {
return
left;
}
if
(right !=
null
) {
return
right;
}
return
null
;
}
}