Frontend Interview

Appearance

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

题目链接：https://leetcode.cn/problems/lowest-common-ancestor-of-a-binary-tree/

代码 ​

ts
/**
 * 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 || root === p || root === q) return root;
    const left = lowestCommonAncestor(root.left, p, q);
    const right = lowestCommonAncestor(root.right, p, q);
    return left && right ? root : (left ? left : right);
};

思路 ​

使用递归后序遍历查找节点 p 和 q：

  1. 如果当前节点为空，返回 null
  2. 如果当前节点等于 p 或 q，直接返回当前节点
  3. 递归查找左子树，得到 left
  4. 递归查找右子树，得到 right
  5. 如果 left 和 right 都不为空，说明 p 和 q 分别位于当前节点两侧，当前节点就是最近公共祖先
  6. 如果只有一侧不为空，说明两个目标节点都在这一侧，继续向上返回该结果

关键点 ​

  • 递归函数的返回值表示：当前子树中是否找到了 p、q 或它们的最近公共祖先

  • 当左右子树分别找到一个目标节点时，当前节点第一次满足“分叉点”条件，即答案

  • 如果当前节点本身就是 p 或 q，也可能成为最近公共祖先

  • 时间复杂度：O(n)，其中 n 是节点数，最坏情况下需要遍历整棵树

  • 空间复杂度：O(h)，其中 h 是树的高度，主要为递归栈开销