230. 二叉搜索树中第K小的元素

题解：

二叉搜索树中序遍历的结果，是升序数组，所以先中序遍历数组，第k个元素即为第k个小的元素。

思路一：

迭代代码如下：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19


    List<Integer> list = new ArrayList<>();
    List<Integer> dfs (TreeNode root){
        if (root == null) return list;

        dfs(root.left);
        list.add(root.val);
        dfs(root.right);

        return list;
    }

	
    public int kthSmallest(TreeNode root, int k) {

        // 获取数组
        dfs(root);
        return list.get(k);
    }

思路二：

递归代码如下：

 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


List<Integer> dfs1(TreeNode root) {
        List<Integer> list = new ArrayList<>();

        Stack<TreeNode> stack = new Stack<>();
        while (!stack.isEmpty() || root != null) {

            while (root != null) {
                stack.push(root);
                root = root.left;
            }

            root = stack.pop();
            list.add(root.val);
            root = root.right;
        }
        return list;
    }

    public int kthSmallest(TreeNode root, int k) {

        // 获取数组
        List<Integer> list = dfs1(root);

        return list.get(k);
    }

上述两种方法中，时间复杂度都是 O(N) ，遍历了树的所有节点。

空间复杂度也是 O(N), 用到了额外的存储N个元素的数组。

优化：

上述解题，我们看出，我们完全不需要遍历整个二叉树，中序遍历到第K位就能求出结果，完全没必要继续遍历。所有下边我们优化

思路三：

优化时间复杂度至 O(K), 空间复杂度至 O(1)

迭代

代码如下：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20


// 优化遍历次数 且不需要额外数组存储
public int dfs(TreeNode root, int k){
    Stack<TreeNode> stack = new Stack<>();

    int count = 0;
    while (!stack.isEmpty() || root != null){
        while (root != null){
            stack.push(root);
            root = root.left;
        }

        root = stack.pop();
        count ++;
        if (count == k) return root.val;

        root = root.right;
    }

    return -1;
}

思路四：