# \#235 Lowest Common Ancestor of a Binary Search Tree
## *給定一個二元搜尋樹, 找到LCA*
## Log
- build 20210515 by syhuang
## 遞迴版
- 實作遞迴版

var lowestCommonAncestor = function(root, p, q) {
    var isBetween = (root.val-p.val)*(root.val-q.val)<0;
    return isBetween?root:
            lowestCommonAncestor(root.val>p.val?root.left:root.right,p,q);
    
};

## 改進初見
- 改進"判斷區間"邏輯: 判斷一個數是否為兩數的區間, 可以對兩數相減之後的乘積正負來判斷(可讀性稍微下降)

var lowestCommonAncestor = function(root, p, q) {
    var node = root;
    while(node){
        if((node.val-p.val)*(node.val-q.val)<=0) break;
        node = (node.val>p.val)?node.left:node.right;
    }
    return node;
};

## 初見
- 基本邏輯:LCA值一定是[p,q], 即介於p和q之間, pq含在內, 實作此邏輯

var lowestCommonAncestor = function(root, p, q) {
    var node = root;
    while(node){
        if(node.val == p.val || node.val == q.val) break;
        if(isBetween(node.val,p.val,q.val)) break;
        node = (node.val>p.val)?node.left:node.right;
    }
    return node;
        
    function isBetween(comp,a,b){//判斷某數是否在a,b區間內(包含ab), ab沒有大小分別
        if(comp<=a && comp>=b) return true;
        if(comp>=a && comp<=b) return true;
        return false;
    }
};

## 備註
- 遞迴和一般解法在時間與空間複雜度上差異不大
## 參考
###### tags: `leetcode`, `leetcode-easy`