問題：
Given a binary search tree (BST), find the lowest common ancestor (LCA) of two given nodes in the BST.
According to the definition of LCA on Wikipedia: “The lowest common ancestor is defined between two nodes v and w as the lowest node in T that has both v and w as descendants (where we allow a node to be a descendant of itself).”
image.png
For example, the lowest common ancestor (LCA) of nodes 2 and 8 is 6. Another example is LCA of nodes 2 and 4 is 2, since a node can be a descendant of itself according to the LCA definition.
大意：
給出一個(gè)二叉查找樹（BST），在其中找到給出的兩個(gè)節(jié)點(diǎn)的最低的共同祖先（LCA）严沥。
根據(jù)維基百科對LCA的定義：“最低共同祖先是指兩個(gè)節(jié)點(diǎn)v和w在T中有v和w作為后代節(jié)點(diǎn)的最低節(jié)點(diǎn)（我們允許節(jié)點(diǎn)是自己的祖先）猜极。”
image.png
比如說消玄，2和8的LCA是6魔吐。另一個(gè)例子，2和4的LCA是2莱找，因?yàn)楦鶕?jù)LCA的定義酬姆，一個(gè)節(jié)點(diǎn)可以是它自己的祖先。
思路：
這里要注意的地方是給出的二叉樹是一個(gè)二叉查找樹奥溺，所謂二叉查找樹是指：
- 若左子樹不空辞色，則左子樹上所有結(jié)點(diǎn)的值均小于它的根結(jié)點(diǎn)的值；
- 若右子樹不空浮定，則右子樹上所有結(jié)點(diǎn)的值均大于它的根結(jié)點(diǎn)的值相满；
- 左、右子樹也分別為二叉排序樹桦卒；
- 沒有鍵值相等的結(jié)點(diǎn)立美。
對于這個(gè)問題，如果是一個(gè)隨意的二叉樹要找LCA是比較麻煩的方灾，要先找到目標(biāo)節(jié)點(diǎn)的位置然后又反過來一層層找最低祖先建蹄。但是對于二叉查找樹就要簡單的多了碌更，因?yàn)槭桥藕眯蛄说模梢院唵蔚卣业轿恢谩?/p>
我們根據(jù)目標(biāo)節(jié)點(diǎn)的值和根節(jié)點(diǎn)的值來判斷目標(biāo)節(jié)點(diǎn)在跟節(jié)點(diǎn)的左子樹上還是右子樹上洞慎，如果一個(gè)在左一個(gè)在右痛单，就說明其LCA是根節(jié)點(diǎn)；如果都在左或者都在右劲腿，就對跟節(jié)點(diǎn)的左或者右子節(jié)點(diǎn)調(diào)用同樣的方法進(jìn)行遞歸旭绒。
因?yàn)闆]有鍵值相等的節(jié)點(diǎn)，所以判斷時(shí)不用考慮等于的情況焦人，這道題中也不需要考慮節(jié)點(diǎn)為null的特殊情況挥吵，所以代碼很簡單。
代碼（Java）：
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if (root.val - p.val > 0 && root.val - q.val > 0) return lowestCommonAncestor(root.left, p, q);
else if (root.val - p.val < 0 && root.val - q.val < 0) return lowestCommonAncestor(root.right, p, q);
else return root;
}
}
合集：https://github.com/Cloudox/LeetCode-Record
