力扣链接：236.二叉树的最近公共祖先

难度：⭐⭐

解题关键词：二叉树、递归

解题思路：使用后序遍历递归判断当前节点是否满足条件，如果该节点的左子树和右子树有两个目标节点，或者当前节点是目标节点的其中一个节点，然后该节点左右子树中包含另外一个节点，那么该节点就是要找的最近公共祖先。

function lowestCommonAncestor(
  root: TreeNode | null,
  p: TreeNode | null,
  q: TreeNode | null
): TreeNode | null {
  // 最后答案
  let ans = null;

  const dfs = (
    root: TreeNode | null,
    p: TreeNode | null,
    q: TreeNode | null
  ) => {
    // 如果当前节点为空，那么不包含目标节点
    if (root === null) return false;

    // 递归判断左子树中是够包含目标节点
    const lSon = dfs(root.left, p, q);
    // 递归判断右子树中是够包含目标节点
    const rSon = dfs(root.right, p, q);

    // 1.左右子树包含两个目标节点
    // 2.当前节点是目标节点其中一个，并且左右子树中包含另一个
    if (
      (lSon && rSon) ||
      ([p.val, q.val].includes(root.val) && (lSon || rSon))
    ) {
      ans = root;
    }

    // 左右子树包含 或者 当前节点是其中一个
    return lSon || rSon || root.val === p.val || root.val === q.val;
  };

  dfs(root, p, q);

  return ans;
}