来自Leetcode第230题二叉搜索树中第K小的元素
给定一个二叉搜索树，编写一个函数 kthSmallest 来查找其中第 k 个最小的元素。
说明：
你可以假设 k 总是有效的，1 ≤ k ≤ 二叉搜索树元素个数。
示例 1:
1
2
3
4
5
6
7
| 输入: root = [3,1,4,null,2], k = 1
3
/ \
1 4
\
2
输出: 1
|
二叉树中序遍历
通过中序遍历按序保存二叉搜索树中的节点值，最后返回K-1位置的值即可。
1
2
3
4
5
6
7
8
9
10
11
12
13
| List<Integer> tree = new ArrayList<>();
public int kthSmallest(TreeNode root, int k) {
helper(root);
return tree.get(k - 1);
}
private void helper(TreeNode root){
if(root == null)
return;
helper(root.left);
tree.add(root.val);
helper(root.right);
}
|
迭代
来源官方题解
在栈的帮助下，可以将方法一的递归转换为迭代，这样可以加快速度，因为这样可以不用遍历整个树，可以在找到答案后停止。
1
2
3
4
5
6
7
8
9
10
11
12
13
| public int kthSmallest(TreeNode root, int k) {
LinkedList<TreeNode> stack = new LinkedList<>();
while(true){
while(root != null){
stack.add(root);
root = root.left;
}
root = stack.removeLast();
if(--k == 0)
return root.val;
root = root.right;
}
}
|
递归
用一个变量记录遍历了的位置，最后返回对应位置的值
1
2
3
4
5
6
7
8
9
10
11
12
13
| int num=0,minimum=0;
public int kthSmallest(TreeNode root, int k) {
if(root==null)return 0;
kthSmallest(root.left,k);
num++;
if(num==k)
{
minimum=root.val;
return minimum;
}
kthSmallest(root.right,k);
return minimum;
}
|