二叉搜索树中第 k 小的元素

问题分析

给定一个二叉搜索树（BST）的层序表示和一个整数 k，要返回其中第 k 小的节点值。BST 的性质是：左子树所有节点值都小于根节点值，右子树所有节点值都大于根节点值。因此，对 BST 进行中序遍历（左→根→右）会得到一个升序序列，第 k 个访问到的节点就是答案。

解题思路

1. 构造二叉树

   • 输入第一行包含两个整数 n 和 k，分别表示节点总数和目标顺序。
   • 第二行给出长度为 n 的层序遍历数组（用 "null" 表示空节点）。
   • 按照下标关系 left = 2*i+1, right = 2*i+2 构建指针链接即可还原二叉树。

2. 中序遍历查找第 k 小

   • 递归或迭代方式进行中序遍历，同时维护一个计数器 count。
   • 每访问一个非空节点，count++；当 count == k 时记录该节点值并提前返回。

复杂度分析

• 时间复杂度：

  • 构建树需要 O(n)
  • 中序遍历最坏访问所有节点 O(n)，平均可提前结束 O(k + h)（h 为树高）
    → 总体 O(n)

• 空间复杂度：

  • 存储节点指针数组 O(n)
  • 递归栈或显式栈最坏 O(n)
    → 总体 O(n)

Python 实现

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

def build_tree(level_order):
    if not level_order or level_order[0] == 'null':
        return None
    
    root = TreeNode(int(level_order[0]))
    queue = [root]
    i = 1
    while i < len(level_order):
        current = queue.pop(0)
        # 构造左子节点
        if i < len(level_order) and level_order[i] != 'null':
            current.left = TreeNode(int(level_order[i]))
            queue.append(current.left)
        i += 1
        # 构造右子节点
        if i < len(level_order) and level_order[i] != 'null':
            current.right = TreeNode(int(level_order[i]))
            queue.append(current.right)
        i += 1
    return root

def kthSmallest(root, k):
    # 中序遍历，计数器+返回值捕获
    count = 0
    result = None
    def inorder(node):
        nonlocal count, result
        if not node or result is not None:
            return
        inorder(node.left)
        count += 1
        if count == k:
            result = node.val
            return
        inorder(node.right)

    inorder(root)
    return result

if __name__ == "__main__":
    import sys
    n, k = map(int, sys.stdin.readline().split())
    arr = sys.stdin.readline().split()
    root = build_tree(arr)
    print(kthSmallest(root, k))

Java 实现

import java.io.*;
import java.util.*;

class TreeNode {
    int val;
    TreeNode left, right;
    TreeNode(int x) { val = x; }
}

public class Main {
    static int count, k, ans;

    // 根据层次遍历构造二叉树
    public static TreeNode buildTree(String[] tokens) {
        if (tokens.length == 0 || tokens[0].equals("null"))
            return null;
        
        TreeNode root = new TreeNode(Integer.parseInt(tokens[0]));
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        int i = 1;
        while (i < tokens.length) {
            TreeNode current = queue.poll();
            // 构造左子节点
            if (i < tokens.length && !tokens[i].equals("null")) {
                current.left = new TreeNode(Integer.parseInt(tokens[i]));
                queue.offer(current.left);
            }
            i++;
            // 构造右子节点
            if (i < tokens.length && !tokens[i].equals("null")) {
                current.right = new TreeNode(Integer.parseInt(tokens[i]));
                queue.offer(current.right);
            }
            i++;
        }
        return root;
    }

    public static void inorder(TreeNode root) {
        if(root == null || ans != Integer.MIN_VALUE) return;
        inorder(root.left);
        if(++count == k) {
            ans = root.val;
            return;
        }
        inorder(root.right);
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] first = br.readLine().split(" ");
        int n = Integer.parseInt(first[0]);
        k = Integer.parseInt(first[1]);
        String[] arr = br.readLine().split(" ");
        TreeNode root = buildTree(arr);
        ans = Integer.MIN_VALUE;
        inorder(root);
        System.out.println(ans);
    }
}

C++ 实现

#include <bits/stdc++.h>
using namespace std;

struct TreeNode {
    int val;
    TreeNode *left, *right;
    TreeNode(int x): val(x), left(nullptr), right(nullptr) {}
};

// 根据层次遍历结果构造二叉树
TreeNode* buildTree(const vector<string>& tokens) {
    if (tokens.empty() || tokens[0] == "null")
        return nullptr;
    
    TreeNode* root = new TreeNode(stoi(tokens[0]));
    queue<TreeNode*> q;
    q.push(root);
    int i = 1;
    while (i < tokens.size()) {
        TreeNode* current = q.front();
        q.pop();
        // 构造左子节点
        if (i < tokens.size() && tokens[i] != "null") {
            current->left = new TreeNode(stoi(tokens[i]));
            q.push(current->left);
        }
        i++;
        // 构造右子节点
        if (i < tokens.size() && tokens[i] != "null") {
            current->right = new TreeNode(stoi(tokens[i]));
            q.push(current->right);
        }
        i++;
    }
    return root;
}

int countK = 0, answer = -1;
void inorder(TreeNode* root, int k) {
    if(!root || answer != -1) return;
    inorder(root->left, k);
    if(++countK == k) {
        answer = root->val;
        return;
    }
    inorder(root->right, k);
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, k;
    cin >> n >> k;
    vector<string> arr(n);
    for(int i = 0; i < n; i++) cin >> arr[i];
    TreeNode* root = buildTree(arr);
    inorder(root, k);
    cout << answer << "\n";
    return 0;
}

题目内容

给定一个二叉搜索树的根节点 $root$ ，和一个整数 $k$，请你设计一个算法查找其中第 $k$ 小的元素（从$1$ 开始计数）。

输入描述

• 第一行有两个整数$n,k$，$n$是$root$的长度
• 第二行为二叉树的序列化数组$root$，节点值之间用空格隔开，空节点用null表示。

输出描述

输出第 $k$ 小的元素。

样例1

输入

5 1
3 1 4 null 2

输出

1

样例2

输入

8 3
5 3 6 2 4 null null 1

输出

3

提示

• 树中的节点数为 $n$ 。
• $1 <= k <= n <= 10^4$
• $0 <= Node.val <= 10^4$