235. Lowest Common Ancestor of a Binary Search Tree

給一個二元搜索樹(BST)，找到其中兩個點最近的祖先節點。

https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-search-tree/

範例
Input: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8
Output: 6
Explanation: 2 和 8 最近的祖先節點為 6 。

二元搜索樹的定義如下。

1. 以左邊節點(left node)作為根的子樹(sub-tree)的所有值都小於根節點(root)
2. 以右邊節點(right node)作為根的子樹(sub-tree)的所有值都大於根節點(root)
3. 任意節點(node)的左、右子樹也分別符合BST的定義
4. 不存在任何鍵值(key/value )相等的節點。

由1,2可知，要找到兩節點最小的祖先節點，只要從根開始往下走，當兩節點分道揚鑣時就是答案。

此外也有可能碰到節點是自己的情況，表示最小祖先節點即為自身。

寫成程式碼如下

	public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {

		int p_val = p.val;
		int q_val = q.val;

		while (root != null) {
			int now = root.val;

			//節點為自己，或是兩節點分道揚鑣時
			if ((p_val == now || q_val == now) || (p_val < now && q_val > now) || (q_val < now && p_val > now)) {
				return root;
			}
			
			//尚未找到祖先節點，判斷要往左或右走
			if (now < p_val && now < q_val) {
				root = root.right;
			} else {
				root = root.left;
			}
		}
		return root;
	}