二叉树最近公共祖先

分类讨论

返回当前节点的情况

当前节点是空节点
当前节点是 p
当前节点是 q

其他

左右子树都找到：返回当前节点
只有左子树找到：返回递归左子树的结果
只有右子树找到：返回递归右子树的结果
左右子树都没有找到：返回空节点


/**
 * Definition for a binary tree node.
 * class TreeNode {
 *     val: number
 *     left: TreeNode | null
 *     right: TreeNode | null
 *     constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.left = (left===undefined ? null : left)
 *         this.right = (right===undefined ? null : right)
 *     }
 * }
 */
 
function lowestCommonAncestor(
  root: TreeNode | null,
  p: TreeNode | null,
  q: TreeNode | null,
): TreeNode | null {
  if (!root || p === root || q === root) {
    return root;
  }
  const left = lowestCommonAncestor(root.left, p, q);
  const right = lowestCommonAncestor(root.right, p, q);
  if (left && right) {
    return root;
  }
  if (left) return left;
  return right;
}