Medium
我自己用的简单的Recursive inOrder traversal做. 这个方法是O(N)的，因为遍历了整棵树，可以稍加改动改进为O(k)，只需要遍历到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);
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);
}
}
可以改进为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);
}
}
