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 1040 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) { DequeTreeNode 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; } }