Kth Smallest Element in a BST

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.

Hint:

Try to utilize the property of a BST.What if you could modify the BST node's structure?The optimal runtime complexity is O(height of BST).

考察二叉树的中序遍历。

private int[] counter = new int[1]; private int[] result = new int[1]; public int kthSmallest(TreeNode root, int k) { if(root == null){ return 0; } else{ if(root.left != null){ kthSmallest(root.left, k); } counter[0]++; //System.out.println("counter:"+counter[0]); if(counter[0] == k){ result[0] = root.val; return root.val; } if(root.right != null){ kthSmallest(root.right, k); } } return result[0]; }