题目描述
给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
说明：
- 所有节点的值都是唯一的。
- p、q 为不同节点且均存在于给定的二叉树中。
解题思路
如果定义函数lowestCommonAncestor就是找到最近公共祖先的话，如果在左子树找到最近公共祖先则直接返回lca(root.left) 的结果，右子树找到最近的祖先同理。如果p在左子树，q在右子树呢？我们不能简单地返回null。所以我们定义了如下的方法：
- 如果在左右子树中任意一个找到了lca，就返回lca。
- 如果只碰到A，就返回A
- 如果只碰到B，就返回B
- 如果都没有，就返回null
- 如果左右的返回都不为空（说明一个有A一个有B），就返回root
class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if (root == null || root == q || root == p) {
return root;
}
TreeNode left = lowestCommonAncestor(root.left, p, q);
TreeNode right = lowestCommonAncestor(root.right, p, q);
if (left != null && right != null) {
return root;
}
if (left != null) {
return left;
}
if (right != null) {
return right;
}
return null;
}
}
