235md.md

LeetCode 235. Lowest Common Ancestor of a Binary Search

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).”

      _6_
    /    \
   2      8
  / \    / \
 0   4  7   9
    / \
   3   5

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.

##翻譯 給一個二元搜尋樹(BST)，再給兩個樹中的節點Node，找出這兩個Node的最低共同祖先節點，根據LCA在維基百科的定義: "最低共同祖先節點，是指在一個Tree T中的Node v, Node w存在一個最低層級共同的祖先T，同時 v與w也可以算是自己的祖先節點"

範例：以上面的樹來看，[2,8]的最低共同祖先節點為6。
[2,4]的最低共同祖先節點為2，因為2也算是自己的祖先節點

##思路 一個BST，若任意節點的左子樹不為空，則左子樹所有節點的值都會比根節點小，從上面的樹可以看到6的左子樹裡面的節點為[2,0,4,3,5]均比6小。

1. 取得根節點root的值，如果值落在目標節點[p,q]之間，代表root就是最低共同祖先節點
2. 如果root比[p,q]都還小，用root.right取代root繼續往下找
3. 如果root比[p,q]都還小，用root.left取代root繼續往下找

##解題

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @param {TreeNode} p
 * @param {TreeNode} q
 * @return {TreeNode}
 */
var lowestCommonAncestor = function(root, p, q) {
    var count = 0;
    
    while(true){
        var value =  root.val;
            
        if(p.val >= value && value >= q.val || p.val <= value && value <= q.val){
            return root;
        } else if(p.val > value && q.val > value){
            root =  root.right;
        } else {
            root =  root.left;
        }
    }
};