Given a binary search tree (BST), find the lowest common ancestor (LCA) of two given nodes in the BST.
這題怎么說(shuō)呢凝化，思路還是蠻清晰的，
引用一下別人的分析：
在二叉查找樹(shù)種蝶棋，尋找兩個(gè)節(jié)點(diǎn)的最低公共祖先嵌赠。
1塑荒、如果a、b都比根節(jié)點(diǎn)小姜挺，則在左子樹(shù)中遞歸查找公共節(jié)點(diǎn)齿税。
2、如果a炊豪、b都比根節(jié)點(diǎn)大凌箕，則在右子樹(shù)中查找公共祖先節(jié)點(diǎn)。
3词渤、如果a陌知、b一個(gè)比根節(jié)點(diǎn)大，一個(gè)比根節(jié)點(diǎn)小掖肋，或者有一個(gè)等于根節(jié)點(diǎn)，則根節(jié)點(diǎn)即為最低公共祖先赏参。
leetcode的solutions里有人用一行寫(xiě)出來(lái)了：
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
return (root.val - p.val) * (root.val - q.val) < 1 ? root :
lowestCommonAncestor(p.val < root.val ? root.left : root.right, p, q);
}
這個(gè)代碼是可以AC的志笼，也就是說(shuō)沿盅，這題不存在p，q為null的情況纫溃，即便有個(gè)testcase 是 [1,2]腰涧。而且不能說(shuō)p.val一定比q.val小。
所以他用了乘法紊浩，而且是用了<1做判斷條件窖铡，說(shuō)明root.val可以等于p或q的value，對(duì)應(yīng)它說(shuō)的它自己的后代可以是自己的ancestor坊谁。
另外需要注意p.val < root.val费彼，而不是<=。
這題還可以用迭代口芍，今天沒(méi)時(shí)間寫(xiě)了箍铲，唉，11：13了鬓椭，還在公司颠猴。時(shí)間不夠用唉。小染。白天工作效率太低了翘瓮。
不說(shuō)了，回家睡覺(jué)了明天還得早起上班裤翩。
