LeetCode 230 / LintCode 902 Kth Smallest Element in a BST

思路

利用BST的性质，进行中序遍历可以得到一个非递减的序列。本题主要考察BST遍历的迭代写法。

复杂度

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

代码

/*** Definition of TreeNode:* public class TreeNode {* public int val;* public TreeNode left, right;* public TreeNode(int val) {* this.val = val;* this.left = this.right = null;* }* }*/public class Solution {
    /*** @param root: the given BST* @param k: the given k* @return: the kth smallest element in BST*/public int kthSmallest(TreeNode root, int k) {
    // write your code hereStack<TreeNode> stack  = new Stack<>();int count = 0;while (root != null) {
    stack.push(root);root = root.left;}while (!stack.isEmpty()) {
    TreeNode node = stack.peek();count++;if (count == k) {
    return node.val;}if (node.right == null) {
    node = stack.pop();while (!stack.isEmpty() && stack.peek().right == node) {
    node = stack.pop();}} else {
    node = node.right;while (node != null) {
    stack.push(node);node = node.left;}}}return 0;}
}