二叉树的最近公共祖先

1676. 二叉树的最近公共祖先 IV

details

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @param {TreeNode[]} nodes
 * @return {TreeNode}
 *
 */
var lowestCommonAncestor = function(root, nodes) {
  // 把 nodes 转换成 hashmap
  const map = Object.create(null);
  for (let node of nodes) {
    map[node.val] = 1;
  }
  return find(root, map);

  //
  function find(root, map) {
    if (root === null) return null;
    if (map[root.val]) {
      return root;
    }
    const left = find(root.left, map);
    const right = find(root.right, map);
    // 左右子树都包含 节点的值
    if (left !== null && right !== null) {
      return root;
    }
    // 其中一个节点就是 LCA
    return left ? left : right;
  }
};

236. 二叉树的最近公共祖先

details

/**
 * 236. 二叉树的最近公共祖先
 *
 * @param {TreeNode} root
 * @param {TreeNode} p
 * @param {TreeNode} q
 * @return {TreeNode}
 */
var lowestCommonAncestor = function(root, p, q) {
  return find(root, p.val, q.val);

  function find(root, p, q) {
    if (!root) return null;
    if (root.val === p || root.val === q) {
      return root;
    }
    const left = find(root.left, p, q);
    const right = find(root.right, p, q);

    if (left && right) {
      return root;
    }
    return left ? left : right;
  }
};

1644. 二叉树的最近公共祖先 II

details

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * 1644. 二叉树的最近公共祖先 II  后序遍历
 *
 * @param {TreeNode} root
 * @param {TreeNode} p
 * @param {TreeNode} q
 * @return {TreeNode}
 */
var lowestCommonAncestor = function(root, p, q) {
  // 标记 值 都需要被找到 ，否则返回null
  let findLeft = false;
  let findRight = false;
  // 2个节点都需要存在
  if (!p || !q) return null;

  const ans = find(root, p.val, q.val);
  if (!findLeft || !findRight) return null;
  return ans;

  function find(root, val1, val2) {
    //
    if (!root) return null;

    const left = find(root.left, val1, val2);
    const right = find(root.right, val1, val2);

    if (left && right) {
      return root;
    }

    if (root.val === val1 || root.val === val2) {
      root.val === val1, (findLeft = true);
      root.val === val2, (findRight = true);
      // 代表找到当前值
      return root;
    }
    return left ? left : right;
  }
};

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

details

/**
 *  235. 二叉搜索树的最近公共祖先
 * @param {TreeNode} root
 * @param {TreeNode} p
 * @param {TreeNode} q
 * @return {TreeNode}
 */
var lowestCommonAncestor = function(root, p, q) {
  const min = p.val < q.val ? p.val : q.val;
  const max = p.val < q.val ? q.val : p.val;
  return find(root, min, max);

  function find(root, min, max) {
    if (!root) return null;
    if (root.val > max) {
      return find(root.left, min, max);
    }
    if (root.val < min) {
      return find(root.right, min, max);
    }
    return root;
  }
};

1650. 二叉树的最近公共祖先 III

details

/**
 * 1650. 二叉树的最近公共祖先 III
 * @param {Node} node
 * @return {Node}
 */
var lowestCommonAncestor = function(p, q) {
  let left = p;
  let right = q;
  while (left !== right) {
    if (!left) {
      left = q;
    } else {
      left = left.parent;
    }

    if (!right) {
      right = p;
    } else {
      right = right.parent;
    }
  }
  return left;
};