Leetcode 230 Kth Smallest Element in a BST

思路

由于bst的中序遍历可以得到一个升序的序列，因此对bst进行中序遍历并记录已经遍历过的数字，当遍历过count==k-1时（count初始为0），说明现在正在遍历的是第k小的数字，保存起来等到最后返回即可。

小技巧

需要注意的是在java的值传递方式，将count和result放到数组中可以随着递归改变值

代码

/*** Definition for a binary tree node.* public class TreeNode {* int val;* TreeNode left;* TreeNode right;* TreeNode(int x) { val = x; }* }*/
class Solution {
    public int kthSmallest(TreeNode root, int k) {
    // info[0] <- count// info[1] <- resultint[] info = new int[2];inorder(root, k, info);return info[1];}public void inorder(TreeNode root, int k, int[] info) {
    if(root == null)return;inorder(root.left, k, info);if(info[0] == k-1) {
    info[1] = root.val;}info[0]++;inorder(root.right, k, info);}
}

复杂度分析

时间复杂度O(n)
空间复杂度O(n)(最坏情况bst为一条线)