LeetCode 230. 二叉搜索树中第 K 小的元素

Categories:

Tags:

题目描述
思路分析
1. 解法一：中序遍历（推荐）
相似题目

题目描述

✅ 230. 二叉搜索树中第 K 小的元素

思路分析

解法一：中序遍历（推荐）

核心思路：

二叉搜索树的中序遍历结果是递增序列。

使用栈做迭代中序遍历，计数到第 k 个结点即返回。

不需要存完整序列，空间更省。

复杂度分析：

时间复杂度：O(h + k)，其中 h 为树高。

空间复杂度：O(h)，栈空间。

class Solution {
    public int kthSmallest(TreeNode root, int k) {
        Deque<TreeNode> stack = new ArrayDeque<>();
        TreeNode cur = root;

        // 中序遍历按序访问结点
        while (cur != null || !stack.isEmpty()) {
            while (cur != null) {
                stack.push(cur);
                cur = cur.left;
            }

            cur = stack.pop();
            if (--k == 0) {
                return cur.val;
            }
            cur = cur.right;
        }

        return -1;
    }
}

func kthSmallest(root *TreeNode, k int) int {
    stack := make([]*TreeNode, 0)
    cur := root

    // 中序遍历按序访问结点
    for cur != nil || len(stack) > 0 {
        for cur != nil {
            stack = append(stack, cur)
            cur = cur.Left
        }

        cur = stack[len(stack)-1]
        stack = stack[:len(stack)-1]
        k--
        if k == 0 {
            return cur.Val
        }
        cur = cur.Right
    }

    return -1
}

相似题目

题目	难度	考察点
94. 二叉树的中序遍历	简单	栈/递归
98. 验证二叉搜索树	中等	BST 性质
173. 二叉搜索树迭代器	中等	中序遍历
538. 把二叉搜索树转换为累加树	中等	反向中序
700. 二叉搜索树中的搜索	简单	BST 性质

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2024/50140221