題目描述
給定一個(gè)二叉搜索樹, 找到該樹中兩個(gè)指定節(jié)點(diǎn)的最近公共祖先默怨。
百度百科中最近公共祖先的定義為：“對于有根樹 T 的兩個(gè)結(jié)點(diǎn) p、q，最近公共祖先表示為一個(gè)結(jié)點(diǎn) x，滿足 x 是 p城侧、q 的祖先且 x 的深度盡可能大（一個(gè)節(jié)點(diǎn)也可以是它自己的祖先）”似蓿”
例如嫌佑，給定如下二叉搜索樹: root = [6,2,8,0,4,7,9,null,null,3,5]
題解
根據(jù)二叉搜索樹的性質(zhì)，左子樹的值小于根節(jié)點(diǎn)的值侨歉，右子樹的值大于根節(jié)點(diǎn)的值屋摇。
因此，如果是根節(jié)點(diǎn)為最近公共祖先幽邓，下面三個(gè)條件滿足一個(gè)即可：
- 節(jié)點(diǎn)p的值等于根節(jié)點(diǎn)的值（此時(shí)p為q的父節(jié)點(diǎn)）
- 節(jié)點(diǎn)q的值等于根節(jié)點(diǎn)的值（此時(shí)q為p的父節(jié)點(diǎn)）
- 當(dāng)p摊册、q分別為根節(jié)點(diǎn)的左孩子和右孩子的時(shí)候
- 當(dāng)p、q分別為根節(jié)點(diǎn)的右孩子和左孩子的時(shí)候
如果三個(gè)條件都不滿足颊艳，那么根節(jié)點(diǎn)就不是最近公共祖先茅特，繼續(xù)往下遞歸就好了：
- 如果p和q的值都小于根節(jié)點(diǎn)的值，那么在左子樹上遞歸（可以只寫p或者q的邏輯棋枕，因?yàn)槿绻鹥的值小于根節(jié)點(diǎn)的值白修，那么q的值就不可能大于根節(jié)點(diǎn)的值了（上面已經(jīng)判斷過））
- 如果p和q的值都大于根節(jié)點(diǎn)的值，那么在右子樹上遞歸（同理）
class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if (p.val == root.val || q.val == root.val || (p.val < root.val && q.val > root.val)
|| (p.val > root.val && q.val < root.val))
return root;
if (p.val < root.val) return lowestCommonAncestor(root.left, p, q);
return lowestCommonAncestor(root.right, p, q);
}
}
