每日一题-20240319

发表于 更新于 分类于 阅读次数： 本文字数： 229 阅读时长 ≈ 1 分钟

题目描述

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

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

示例 1：

img

1
2
输入：root = [3,1,4,null,2], k = 1
输出：1

示例 2：

img

1
2
输入：root = [5,3,6,2,4,null,null,1], k = 3
输出：3

提示：

  • 树中的节点数为 n 。
  • 1 <= k <= n <= 104
  • 0 <= Node.val <= 104

解题思路

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public class Solution230Case1 {
    public int kthSmallest(TreeNode root, int k) {
        List<Integer> list = new ArrayList<>();
        inOrder(root, list);
        return list.get(k - 1);
    }

    public void inOrder(TreeNode node, List<Integer> list) {
        if (null == node) {
            return;
        }
        // 访问优先级：左子树 -> 根节点 -> 右子树
        // 遍历左节点
        inOrder(node.left, list);
        // 逻辑处理
        list.add(node.val);
        // 遍历右节点
        inOrder(node.right, list);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public class Solution230Case2 {
    public int kthSmallest(TreeNode root, int k) {
        Deque<TreeNode> stack = new ArrayDeque<TreeNode>();
        while (root != null || !stack.isEmpty()) {
            while (root != null) {
                stack.push(root);
                root = root.left;
            }
            root = stack.pop();
            --k;
            if (k == 0) {
                break;
            }
            root = root.right;
        }
        return root.val;
    }
}