How do I approach the Lowest Common Ancestor problem in a Binary Search Tree?

Start by utilizing the BST property to narrow down the search direction. Use DFS to explore the tree and track the state of traversal to identify the LCA.

What is the key traversal method for solving the Lowest Common Ancestor problem?

The primary traversal method is Depth-First Search (DFS), where you explore each subtree and determine if both nodes are present in the same subtree.

What should I consider when analyzing the time complexity for this problem?

The time complexity depends on the tree's height, which is O(log n) for a balanced tree and O(n) for a skewed tree. Space complexity is O(h) for a recursive approach.

What is the significance of the binary search tree property in this problem?

The binary search tree property allows for efficient traversal and narrowing down the search for the LCA by checking whether the nodes lie in the left or right subtree of the current node.

How can GhostInterview help me with the Lowest Common Ancestor problem?

GhostInterview provides a structured approach, highlighting the critical traversal patterns and common pitfalls to avoid, ensuring an efficient and clear solution.

#235

Medium

auto_awesome二分·树·traversal

LeetCode 题解工作台

二叉搜索树的最近公共祖先

给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。” 例如，给定如下二叉…

树深度优先搜索二叉搜索树二叉树

题目描述

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

百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”

例如，给定如下二叉搜索树: root = [6,2,8,0,4,7,9,null,null,3,5]

示例 1:

输入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8
输出: 6 
解释: 节点 2 和节点 8 的最近公共祖先是 6。

示例 2:

输入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 4
输出: 2
解释: 节点 2 和节点 4 的最近公共祖先是 2, 因为根据定义最近公共祖先节点可以为节点本身。

说明:

所有节点的值都是唯一的。
p、q 为不同节点且均存在于给定的二叉搜索树中。

lightbulb

解题思路

方法一：迭代

我们从根节点开始遍历，如果当前节点的值小于 $\textit{p}$ 和 $\textit{q}$ 的值，说明 $\textit{p}$ 和 $\textit{q}$ 应该在当前节点的右子树，因此将当前节点移动到右子节点；如果当前节点的值大于 $\textit{p}$ 和 $\textit{q}$ 的值，说明 $\textit{p}$ 和 $\textit{q}$ 应该在当前节点的左子树，因此将当前节点移动到左子节点；否则说明当前节点就是 $\textit{p}$ 和 $\textit{q}$ 的最近公共祖先，返回当前节点即可。

时间复杂度 $O(n)$ ，其中 $n$ 是二叉搜索树的节点个数。空间复杂度 $O(1)$ 。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

# 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':
        while 1:
            if root.val < min(p.val, q.val):
                root = root.right
            elif root.val > max(p.val, q.val):
                root = root.left
            else:
                return root

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Candidate correctly identifies the LCA concept and binary search tree traversal patterns.
question_mark
Candidate efficiently explains the use of DFS and state tracking in LCA search.
question_mark
Candidate discusses time and space complexities relevant to the tree's structure and traversal.

warning

常见陷阱

外企场景

error
Confusing binary tree traversal with BFS, leading to inefficient solutions.
error
Incorrectly identifying the LCA when both nodes are in the same subtree.
error
Not considering the edge case where one of the nodes is the root.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Find the LCA for multiple pairs of nodes in a single BST.
arrow_right_alt
Find the LCA in a binary tree (not necessarily a BST).
arrow_right_alt
Find the LCA in a tree with non-unique node values.

help

常见问题

外企场景

继续练习

#230 二叉搜索树中第 K 小的元素 #99 恢复二叉搜索树 #98 验证二叉搜索树