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.
Follow up: What if the BST is modified (insert/delete operations) often and you need to find the kth smallest frequently? How would you optimize the kthSmallest routine?
Credits: Special thanks to @ts for adding this problem and creating all test cases.
根据BST的性质，一路向左下找到最小的，同时一路push，到底了pop一个得到1th small，有右节点的话push进去，再次一路push，找到2th small，依此类推。代码如下： /** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ public class Solution { public int kthSmallest(TreeNode root, int k) { Stack<TreeNode> stack = new Stack<TreeNode>(); HashSet<TreeNode> hs = new HashSet<TreeNode>(); TreeNode resNode = null; stack.push(root); while (k > 0) { while (stack.peek().left != null && !hs.contains(stack.peek().left)) { stack.push(stack.peek().left); } k --; resNode = stack.pop(); hs.add(resNode); if (resNode.right != null) { stack.push(resNode.right); } } return resNode.val; } }第二种是DFS递归的方法。代码如下： public int kthSmallest(TreeNode root, int k) { int count = countNodes(root.left); if (k <= count) { return kthSmallest(root.left, k); } else if (k > count + 1) { return kthSmallest(root.right, k-1-count); // 1 is counted as current node } return root.val; } public int countNodes(TreeNode n) { if (n == null) return 0; return 1 + countNodes(n.left) + countNodes(n.right); }第三种方法，中序遍历。代码如下： // better keep these two variables in a wrapper class private static int number = 0; private static int count = 0; public int kthSmallest(TreeNode root, int k) { count = k; helper(root); return number; } public void helper(TreeNode n) { if (n.left != null) helper(n.left); count--; if (count == 0) { number = n.val; return; } if (n.right != null) helper(n.right); }