描述
给定一棵二叉树，找到两个节点的最近公共父节点(LCA)。
最近公共祖先是两个节点的公共的祖先节点且具有最大深度。
注意事项
假设给出的两个节点都在树中存在
样例
对于下面这棵二叉树
4
/ \
3 7
/ \
5 6
LCA(3, 5) = 4
LCA(5, 6) = 7
LCA(6, 7) = 7
PS
祖先的定义中自己也是自己的祖先
代码
/**
* 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;
* }
* }
*/
// 本题的最终返回结果是无法判断最终的返回值到底是两结点的LCA，
// 还是树中只有A返回A，还是树中只有B返回B
public class Solution {
// 在root为根的二叉树中找A,B的LCA:
// 如果找到了就返回这个LCA
// 如果只碰到A，就返回A
// 如果只碰到B，就返回B
// 如果都没有，就返回null
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode node1, TreeNode node2) {
// 递归的出口
if (root == null || root == node1 || root == node2) {
return root;
}
// Divide
TreeNode left = lowestCommonAncestor(root.left, node1, node2);
TreeNode right = lowestCommonAncestor(root.right, node1, node2);
// A 和 B 一个在左子树，一个在右子树的情形
if (left != null && right != null) {
return root;
}
// A 和 B 都在左子树
if (left != null) {
return left;
}
// A 和 B 都在右子树
if (right != null) {
return right;
}
return null;
}
}
