二叉搜索树中第k小的元素

发表于 更新于 分类于 阅读次数：

二叉搜索树中第K小的元素（难度：中等）

1579620616705
1579620662544

此题与二叉树的中序遍历（难度：中等）类似，只需稍加变化。

方法一：递归

通过构造 BST 的中序遍历序列，则第 k-1 个元素就是第 k 小的元素。

7dc3fe454519e27105c5aaf57d20b26137bd77c56bb0289830bf18116627de12-file_1579413216156
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
/**
 * 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<Integer> arr = new ArrayList<>();
        inorder(root,arr);
        return arr.get(k-1);
    }

    public void inorder(TreeNode root, List arr){
        if(root!=null){
            if(root.left!=null)
                inorder(root.left, arr);
            arr.add(root.val);
            if(root.right!=null)
                inorder(root.right, arr);
        }
    }
}
1579620513520
复杂度

时间复杂度：O(N)，遍历了整个树。

空间复杂度：O(N)，用了一个数组存储中序序列。

方法二：迭代

在栈的帮助下，可以将方法一的递归转换为迭代，这样可以加快速度，因为这样可以不用遍历整个树，可以在找到答案后停止。

25159a5137867644b75f203ee1917645d2cd454d8f4871e371d7edfa67bef083-file_1579413216176
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def kthSmallest(self, root: TreeNode, k: int) -> int:
        stack = []
        while True:
            while root:
                stack.append(root)
                root = root.left
            root = stack.pop()
            k -= 1
            if k == 0:
                return root.val
            root = root.right

1579621550313
复杂度

时间复杂度：O(H+k)，其中 H指的是树的高度，由于我们开始遍历之前，要先向下达到叶，当树是一个平衡树时：复杂度为O(logN+k)。当树是一个不平衡树时：复杂度为 O(N+k)，此时所有的节点都在左子树。

空间复杂度：O(H+k)。当树是一个平衡树时：O(logN+k)。当树是一个非平衡树时：O(N+k)。