二叉(搜索)树的最近公共祖先

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

LeetCode-235

// 注意p与q也是树节点，比较其值时取val
var lowestCommonAncestor = function(root, p, q) {
  // 基于二叉搜索树的特性
  while(root) {
    // 根节点的val同时大于p和q的val，说明两个节点在根节点的左边
    if(root.val > p.val && root.val > q.val) {
        root = root.left
    // 根节点的val同时小于p和q的val，说明两个节点在根节点的右边
    } else if (root.val < p.val && root.val < q.val) {
        root = root.right
    // 如果一大一小，说明节点位于二叉搜索树的根节点，本身为公共祖先节点
    } else {
        return root
    }
  }
}

二叉树的最近公共祖先

LeetCode-236

var lowestCommonAncestor = function(root, p, q) {
  // 终止条件，边界或者查找到节点
  if(root === null || root === p || root === q) return root
  let left = lowestCommonAncestor(root.left, p, q) // 递归左子树
  let right = lowestCommonAncestor(root.right, p, q) // 递归右子树

  // 如果在某一个节点的左右子树同时能找到p和q说明这个节点就是公共祖先
  if(left !== null && right !== null) return root
  // 如果左子树没找到，说明p，q都在右子树
  if(left === null) return right
  // 如果右子树没找到，说明p，q都在左子树
  if(right === null) return left
}