235. 二叉搜索树的最近公共祖先

[shengxinjing]

给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。

百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”

例如，给定如下二叉搜索树:  root = [6,2,8,0,4,7,9,null,null,3,5]

 

示例 1:

输入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8 输出: 6 解释: 节点 2 和节点 8 的最近公共祖先是 6。 示例 2:

输入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 4 输出: 2 解释: 节点 2 和节点 4 的最近公共祖先是 2, 因为根据定义最近公共祖先节点可以为节点本身。  

说明:

所有节点的值都是唯一的。 p、q 为不同节点且均存在于给定的二叉搜索树中。

来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/lowest-common-ancestor-of-a-binary-search-tree 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

[kaizige10]

// 思路：迭代。
// 利用二叉搜索树的性质：左子树均小于根，右子树均大于根
// 那么比较p、q和cur的大小可以直接判断下一步应该去左子树还是右子树查找
var lowestCommonAncestor = function(root, p, q) {
    let cur = root
    while(cur) {
        // p和q在cur左右两侧，或者p就是cur，或者q就是cur
        if ((p.val < cur.val && q.val > cur.val) || (p.val > cur.val && q.val < cur.val) || 
p.val == cur.val || q.val == cur.val) return cur
        if (p.val < cur.val) {
            // p和q在左侧
            cur = cur.left
        } else {
            // p和q在右侧
            cur = cur.right
        }
    }
};

[javin9]

var lowestCommonAncestor = function (root, p, q) {
  var val = root.val
  var pVal = p.val
  var qVal = q.val
  if (pVal > qVal) {
    var tmp = qVal
    qVal = pVal
    pVal = tmp
  }

  //第一种情况：左子树一个，右字数一个
  if (pVal < val && qVal > val) {
    return root
  }
  //第二种情况：都在左子树
  if (pVal < val && qVal < val) {
    return lowestCommonAncestor(root.left, p, q)
  }

  //第三种情况：都在右子树
  if (pVal > val && qVal > val) {
    return lowestCommonAncestor(root.right, p, q)
  }
  //第四种情况：有一个值等于root的值
  if (pVal === val || qVal === val) {
    return root
  }

};