236.Lowest Common Ancestor of a Binary Tree

/**
 * 寻找二叉树中两个节点的最近公共祖先
 * @param {TreeNode} root - 二叉树的根节点
 * @param {TreeNode} p - 目标节点1
 * @param {TreeNode} q - 目标节点2
 * @returns {TreeNode} 最近公共祖先节点
 */
function lowestCommonAncestor(root, p, q) {
  // 递归终止条件：
  // 1. 遍历到空节点（说明当前路径没有找到p/q）
  // 2. 找到p节点或q节点（直接返回该节点，作为找到的标记）
  if (root === null || root === p || root === q) {
    return root
  }

  // 递归遍历左子树，寻找p或q
  const left = lowestCommonAncestor(root.left, p, q)
  // 递归遍历右子树，寻找p或q
  const right = lowestCommonAncestor(root.right, p, q)

  // 情况1：左子树和右子树都没找到p/q，说明当前节点的子树中无目标节点，返回null
  if (left === null && right === null) {
    return null
  }

  // 情况3：左子树没找到，右子树找到了，说明p/q都在右子树中，返回右子树找到的节点
  if (left === null) {
    return right
  }

  // 情况4：右子树没找到，左子树找到了，说明p/q都在左子树中，返回左子树找到的节点
  if (right === null) {
    return left
  }

  // 情况2：左子树和右子树都找到了目标节点（一个在左、一个在右）
  // 说明当前root就是最近公共祖先，返回root
  return root
}

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        # 只要当前根节点是p和q中的任意一个，就返回（因为不能比这个更深了，再深p和q中的一个就没了）
        if not root or root == p or root == q:
            return root
        # 根节点不是p和q中的任意一个，那么就继续分别往左子树和右子树找p和q
        # left和right为 p 或者 q 或者 None
        left = self.lowestCommonAncestor(root.left, p, q)
        right = self.lowestCommonAncestor(root.right, p, q)
        # p和q都没找到，那就没有
        if left == None and right == None:
            return None
        # 左子树没有p也没有q，就返回右子树的结果
        if left == None:
            return right
        # 右子树没有p也没有q就返回左子树的结果
        if right == None:
            return left
        # 左右子树都找到p和q了，那就说明p和q分别在左右两个子树上，所以此时的最近公共祖先就是root
        return root