← 返回博客列表
VO Uber

Uber VO 真题复盘｜二叉搜索树第k大元素 + 反向中序遍历完整解析

2026-03-16

Uber VO 真题复盘｜二叉搜索树第k大元素 + 反向中序遍历完整解析

导读：Uber 的 VO（Virtual Onsite）面试经常考察树形数据结构的深度理解。"二叉搜索树中找第k大元素"是一道经典题目，考察候选人对 BST 性质的理解、递归遍历的掌握，以及问题澄清和优化能力。

本文深度复盘这道真题，包括面试中的关键澄清、算法设计、复杂度分析，以及如何处理多个k值的优化方案。

📌 题目描述

问题陈述

给定一个二叉搜索树（BST）和一个正整数 k，找到二叉搜索树中的第k大元素。

示例：

        10
       /  \
      4    20
     / \     \
    2   5     40

如果 k = 3，输出应为 15
如果 k = 5，输出应为 4

排序顺序：40 > 20 > 15 > 10 > 5 > 4 > 2

🎯 面试中的关键澄清

澄清 1：树的大小假设

问题：是否可以假设二叉树至少包含 k 个元素？

面试官回答：是的，可以假设树至少包含 k 个元素。

意义：这简化了问题，我们不需要处理 k 超出范围的情况。

澄清 2：错误处理

问题：如果树的大小小于 k，应该返回什么？

候选人建议：返回 -1 可能会引起混淆，因为 -1 可能是树中的有效值。建议抛出一个错误。

面试官同意：这是一个很好的观察，展示了候选人的细致思考。

澄清 3：数据结构定义

问题：是否需要定义树节点类？

面试官回答：是的，需要定义 TreeNode 类，以确保候选人能够构建和操作二叉搜索树。

💡 算法设计

核心思想：反向中序遍历

利用 BST 的性质：中序遍历得到升序序列。因此，反向中序遍历得到降序序列。

反向中序遍历顺序：右子树 → 根节点 → 左子树

详细步骤

以示例树为例，找第 3 大元素：

1. 从根节点 10 开始，向右移动到 20
2. 继续向右移动到 40
3. 40 没有右子节点，访问 40（计数 = 1）
4. 回到 20，访问 20（计数 = 2）
5. 移动到 20 的左子节点 15，访问 15（计数 = 3）✓ 找到！

Python 完整代码

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

class KthLargestFinder:
    def __init__(self):
        self.count = 0
        self.result = None
    
    def kthLargest(self, root, k):
        """
        找到 BST 中第 k 大的元素
        
        时间复杂度：O(n)（最坏情况）
        空间复杂度：O(h)（递归栈深度）
        """
        self.count = 0
        self.result = None
        self._reverse_inorder(root, k)
        
        if self.result is None:
            raise ValueError(f"树中没有第 {k} 大的元素")
        
        return self.result
    
    def _reverse_inorder(self, node, k):
        """反向中序遍历"""
        if node is None:
            return
        
        # 先遍历右子树（较大的值）
        self._reverse_inorder(node.right, k)
        
        # 访问当前节点
        self.count += 1
        if self.count == k:
            self.result = node.val
            return
        
        # 再遍历左子树（较小的值）
        self._reverse_inorder(node.left, k)

# 测试用例
if __name__ == "__main__":
    # 构建示例树
    root = TreeNode(10)
    root.left = TreeNode(4)
    root.right = TreeNode(20)
    root.left.left = TreeNode(2)
    root.left.right = TreeNode(5)
    root.right.right = TreeNode(40)
    
    finder = KthLargestFinder()
    
    print(f"第 3 大元素：{finder.kthLargest(root, 3)}")  # 输出：15
    print(f"第 5 大元素：{finder.kthLargest(root, 5)}")  # 输出：4

📊 复杂度分析

指标 复杂度 说明
时间复杂度 O(n) 最坏情况需要遍历所有节点
空间复杂度 O(h) 递归栈深度等于树的高度

优化：如果树是平衡的，h = O(log n)，则空间复杂度为 O(log n)。

🔥 扩展问题：多个 k 值

问题

如何在一次遍历中找到多个 k 值对应的元素？

解决方案

def kthLargestMultiple(root, k_values):
    """
    一次遍历找到多个 k 值对应的元素
    
    时间复杂度：O(n)
    空间复杂度：O(h + m)，m 为 k 值的个数
    """
    k_set = set(k_values)
    max_k = max(k_values)
    results = {}
    count = [0]  # 使用列表以便在嵌套函数中修改
    
    def reverse_inorder(node):
        if node is None or count[0] >= max_k:
            return
        
        # 遍历右子树
        reverse_inorder(node.right)
        
        # 访问当前节点
        count[0] += 1
        if count[0] in k_set:
            results[count[0]] = node.val
        
        if count[0] >= max_k:
            return
        
        # 遍历左子树
        reverse_inorder(node.left)
    
    reverse_inorder(root)
    return results

# 测试
result = kthLargestMultiple(root, [1, 3, 5])
print(result)  # {1: 40, 3: 15, 5: 4}

🎓 面试要点总结

关键知识点

✅ BST 性质 - 中序遍历得升序，反向中序得降序
✅ 递归遍历 - 理解递归调用栈的深度
✅ 问题澄清 - 边界条件、错误处理、数据结构定义
✅ 优化思路 - 从单个 k 值扩展到多个 k 值

Follow-up 问题

🚀 VO 面试辅助策略

VO 面试

📚 相关资源

官方资源

学习资源

社区讨论

💼 需要专业辅助？

oavoservice 提供专业的 Uber VO 辅助服务：

✅ VO 辅助 - 实时提供思路和代码提示
✅ 面试代面 - 资深工程师全程陪同
✅ 系统设计辅导 - 帮助你理解大厂思维
✅ 模拟面试 - 提前适应面试环境

联系方式

为尽快联系和评估，请注明：

发布日期：2026年3月16日
难度：⭐⭐⭐⭐ (中等偏难)
标签：Uber, VO代做, VO辅助, 面试代面, 二叉搜索树, 反向中序遍历, 树形DP, 系统设计

更新历史：