資料內(nèi)容：
基本思路
經(jīng)典問題了，先給出遞歸函數(shù)的定義：給該函數(shù)輸?三個參數(shù) root，p，q，它會返回?個節(jié)點：
情況 1，如果 p 和 q 都在以 root 為根的樹中，函數(shù)返回的即使 p 和 q 的最近公共祖先節(jié)點。
情況 2，那如果 p 和 q 都不在以 root 為根的樹中怎么辦呢？函數(shù)理所當然地返回 null 唄。
情況 3，那如果 p 和 q 只有?個存在于 root 為根的樹中呢？函數(shù)就會返回那個節(jié)點。
根據(jù)這個定義，分情況討論：
情況 1，如果 p 和 q 都在以 root 為根的樹中，那么 left 和 right ?定分別是 p 和 q（從 base case 看出
來的）。
情況 2，如果 p 和 q 都不在以 root 為根的樹中，直接返回 null。
情況 3，如果 p 和 q 只有?個存在于 root 為根的樹中，函數(shù)返回該節(jié)點。
詳細題解：Git原理之最近公共祖先
解法代碼
class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p,
TreeNode q) {
// base case
if (root == null) return null;
if (root == p || root == q) return root;
TreeNode left = lowestCommonAncestor(root.left, p, q);
TreeNode right = lowestCommonAncestor(root.right, p, q);
// 情況 1
if (left != null && right != null) {
return root;
}
// 情況 2
if (left == null && right == null) {
return null;
}
// 情況 3
return left == null ? right : left;
}
}
