二叉树的最近公共祖先

/*
 * 题目：二叉树的最近公共祖先
 * 要求：输入普通二叉树根节点 root（节点含 value、left、right）及节点引用 p、q；按节点身份而非 value 比较，节点也视为自己的祖先。两节点均在树中时返回最近公共祖先节点，否则返回 null；p===q 时若该节点在树中就返回它。
 * 示例：根 3 的左右子节点分别为 5、1，输入 p=节点5、q=节点1，返回根节点3；q 不在树中时返回 null。
 */
function lowestCommonAncestor(root, p, q) {}
const n5 = { value: 5, left: null, right: null };
const n1 = { value: 1, left: null, right: null };
const root = { value: 3, left: n5, right: n1 };
console.log(lowestCommonAncestor(root, n5, n1) === root); // 预期：true
console.log(lowestCommonAncestor(root, n5, n5) === n5); // 预期：true
console.log(lowestCommonAncestor(root, n5, { value: 9 }) === null); // 预期：true
console.log(lowestCommonAncestor(null, n5, n1) === null); // 预期：true

class TreeNode {
  constructor(value, left = null, right = null) {
    this.value = value;
    this.left = left;
    this.right = right;
  }
}
function lowestCommonAncestor(root, p, q) {
  if (!p || !q) return null;
  if (p === q) {
    const contains = (node) =>
      node ? node === p || contains(node.left) || contains(node.right) : false;
    return contains(root) ? p : null;
  }
  function solve(node) {
    if (!node) return { found: 0, candidate: null };
    const left = solve(node.left);
    if (left.candidate) return left;
    const right = solve(node.right);
    if (right.candidate) return right;
    const found = left.found + right.found + (node === p || node === q ? 1 : 0);
    return { found, candidate: found === 2 ? node : null };
  }
  const result = solve(root);
  return result.found === 2 ? result.candidate : null;
}

// 三组以上可直接运行的验证。
const n5 = { value: 5, left: null, right: null };
const n1 = { value: 1, left: null, right: null };
const root = { value: 3, left: n5, right: n1 };
console.log(lowestCommonAncestor(root, n5, n1) === root); // 预期：true
console.log(lowestCommonAncestor(root, n5, n5) === n5); // 预期：true
console.log(lowestCommonAncestor(root, n5, { value: 9 }) === null); // 预期：true
console.log(lowestCommonAncestor(null, n5, n1) === null); // 预期：true