Medium
我自己用的簡(jiǎn)單的Recursive inOrder traversal做. 這個(gè)方法是O(N)的，因?yàn)楸闅v了整棵樹(shù)，可以稍加改動(dòng)改進(jìn)為O(k)，只需要遍歷到k個(gè)就停.

/**
 * 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) {
        List<TreeNode> inOrderRes = new ArrayList<>();
        inOrder(root, inOrderRes);
        return inOrderRes.get(k - 1).val;
    }
    
    private void inOrder(TreeNode root, List<TreeNode> inOrderRes){
        if (root == null){
            return;
        }
        inOrder(root.left, inOrderRes);
        inOrderRes.add(root);
        inOrder(root.right, inOrderRes);
    }
}

可以改進(jìn)為O(K)

/**
 * 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) {
        List<TreeNode> inOrderRes = new ArrayList<>();
        inOrder(root, inOrderRes, k);
        return inOrderRes.get(k - 1).val;
    }
    
    private void inOrder(TreeNode root, List<TreeNode> inOrderRes, int k){
        if (root == null || inOrderRes.size() >= k){
            return;
        }
        inOrder(root.left, inOrderRes, k);
        inOrderRes.add(root);
        inOrder(root.right, inOrderRes, k);
    }
}