LeetCode230-二叉搜索树中第K小的元素

LeetCode230-二叉搜索树中第K小的元素

递归实现(指数级复杂度)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
List<Integer> list = new ArrayList<>();

public int kthSmallest(TreeNode root, int k) {
//中序递归
inorderTraversal(root);
return list.get(k-1);
}

private void inorderTraversal(TreeNode root) {
if (root == null) return;
inorderTraversal(root.left);
System.out.println(root.val);
list.add(root.val);
inorderTraversal(root.right);
}

待改进