JAVA练习312- 二叉搜索树中第 K 小的元素

题目概览

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

示例 1：

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

示例 2：

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

提示：

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

进阶：如果二叉搜索树经常被修改（插入/删除操作）并且你需要频繁地查找第k小的值，你将如何优化算法？

来源：230. 二叉搜索树中第 K 小的元素 - 力扣（LeetCode）

解题分析

方法：中序遍历

中序遍历是 左-根-右，遍历出来的数一定是递增的，因此我们只需要在遍历时记录次数，返回第 k 个节点。

时间复杂度：O(k)
空间复杂度：O(n)

/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; * } * } */ class Solution { public int kthSmallest(TreeNode root, int k) { Deque<TreeNode> dq = new LinkedList<>(); while(root != null || !dq.isEmpty()) { while(root != null) { dq.push(root); root = root.left; } TreeNode node = dq.pop(); if (k-- == 1) { return node.val; } root = node.right; } return -1; } }