题目描述

Given a binary search tree, write a function kthSmallest to find the kth smallest element in it.

Note:
You may assume k is always valid, 1 ≤ k ≤ BST’s total elements.

方法思路

求一组数中的第K个最小值是类非常经典的题目，看到这道题，可以利用BST左小右大的特性，通过中序遍历，将节点的值升序排列，这样当计数到K的时候直接返回就可以了。

class Solution {
    //Runtime: 0 ms, faster than 100.00%
    //Memory Usage: 39.6 MB, less than 8.17%
    public int kthSmallest(TreeNode root, int k) {
       //List<Integer> list = new ArrayList<>();
        Stack<TreeNode> stk = new Stack<>();
        int count =  0;
        TreeNode curr = root;
        while(curr != null || !stk.isEmpty()){
            while(curr != null){
                stk.push(curr);
                curr = curr.left;
            }
            curr = stk.pop();
            count++;
            if(count == k) return curr.val;
            //list.add(curr.val);
            curr = curr.right;
        }
        return 0;
    }
}