Given a binary search tree, write a function kthSmallest to find the kth smallest element in it.
求一个二叉搜索树的第k小值。
题目链接：https://leetcode.com/problems/kth-smallest-element-in-a-bst/
先来看下二叉搜索树的性质，对于任意一个非叶子节点，它的左子树中所有的值必定小于这个节点的val，右子树中所有的值必定大于或等于当前节点的val。 这条性质就保证了如果我们对二叉搜索树做中序遍历，中序遍历的结果肯定是有序的。对于此题而言，我们只需要拿到中序遍历结果，然后返回第k个即可，时间复杂度是O(n)。
但是，其实是有更优的解决方案的，我们只需要第k的数，并不需要遍历整个BST。这个时候，我们只需要把中序遍历的递归代码稍作改造即可，加一个全局遍历count来计数当前遍历到第几个数。因为上面所说的性质，中序遍历是有序的，所以只需要在计数器到k时返回当前节点的val，这就是我们需要的结果，时间复杂度O(k)。
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ public class Solution { private int count = 0; public int kthSmallest(TreeNode root, int k) { if (root == null) return 0; int ret=kthSmallest(root.left, k); if (0 != ret) return ret; if(++count == k) return root.val; return kthSmallest(root.right, k); } }
