LeetCode hot100——二叉搜索树中第 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小的值，你将如何优化算法？

题解

/** * 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) { int num = 0; Deque<TreeNode> stk = new LinkedList<TreeNode>(); while(!stk.isEmpty() || root != null){ while(root != null){ stk.push(root); root = root.left; } root = stk.pop(); num++; if(num == k){ return root.val; } root = root.right; } return 0; } }