Medium
我自己用的簡單的Recursive inOrder traversal做. 這個方法是O(N)的秦驯，因?yàn)楸闅v了整棵樹贡翘，可以稍加改動改進(jì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);
}
}
可以改進(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);
}
}
