Skip to main content

二叉树的最近公共祖先

Tips

题目类型: Tree

题目​

给定一个二叉树, 找到该树中两个指定节点的最近公共祖先.

最近公共祖先的定义为: "对于有根树 T 的两个节点 p 和 q, 最近公共祖先表示为一个节点 x, 满足 x 是 p 和 q 的祖先且 x 的深度尽可能大(一个节点也可以是它自己的祖先).

示例
     3
   /   \
  5     1
 / \    / \
6   2   0  8
   / \
  7   4
输入: p = 5, q = 1
输出: 3
解释: 节点 5 和节点 1 的最近公共祖先是节点 3
输入: p = 5, q = 4
输出: 5
解释: 节点 5 和节点 4 的最近公共祖先是节点 5, 因为根据定义最近公共祖先节点可以为节点本身

题解​

递归函数的定义​

本题为 LCA(最近公共祖先) 的经典算法, git 里的 merge 其实就是利用了该算法.

  1. 如果 left 和 right 都不为空, 则说明 p 和 q 分别在 root 的左右子树中, 因此 root 就是它们的最近公共祖先, 返回 root.
  2. 如果 left 不为空, 而 right 为空, 则说明 p 和 q 都在 root 的左子树中, 返回 left.
  3. 如果 right 不为空, 而 left 为空, 则说明 p 和 q 都在 root 的右子树中, 返回 right.
  4. 如果 left 和 right 都为空, 则说明 p 和 q 在以 root 为根的子树中都不存在, 返回 null.

对于上面的代码, 因为我们使用的后序遍历, 即从下往上走, 因此递归结束的返回值, 也就是离 p, q 最近的了.

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @param {TreeNode} p
 * @param {TreeNode} q
 * @return {TreeNode}
 */
var lowestCommonAncestor = function (root, p, q) {
  if (!root) return null

  if (root === p || root === q) return root

  const left = lowestCommonAncestor(root.left, p, q)
  const right = lowestCommonAncestor(root.right, p, q)

  if (left && right) return root

  return left ? left : right
}
  • 时间复杂度: O(n), 其中 n 是二叉树的节点数. 最坏情况下, 需要遍历所有节点.
  • 空间复杂度: O(h), 其中 h 是二叉树的高度. 最坏情况下, 树退化成链表, h = n, 空间复杂度为 O(n). 最好情况下, 树为完全二叉树, h = logn, 空间复杂度为 O(logn).