230. Kth Smallest Element in a BST
in leetcode with 0 comment

230. Kth Smallest Element in a BST

in leetcode with 0 comment

230. Kth Smallest Element in a BST

原题地址 230. Kth Smallest Element in a BST

解题思路

由于给的二叉搜索树,总所周知二叉搜索树的中序遍历是有序的。所以这题可以变相的理解的为有序数组的中的第k个数

二叉树的中路遍历有两种方法, 递归、非递归(借助 栈).

我们先看递归

递归解法-1

我们通过中序遍历,把遍历的值存在List<Integer> res 中, 然后返回res.get(k -1) 即,.很容易写出如下代码.

AC代码

public int kthSmallest(TreeNode root, int k) {
    ArrayList<Integer> res = new ArrayList<>();
    inorder(root, res);
    return res.get(k - 1);
}

private ArrayList<Integer> inorder(TreeNode root, ArrayList<Integer> res) {
    if (root == null) {
        return res;
    }
    inorder(root.left, res);
    res.add(root.val);
    inorder(root.right, res);
    return res;
}

很明显时间复杂是O(n),空间复杂度是O(n).

递归解法-2

其实我们没用必要记录每个节点的值, 我们只需要遍历到第k个节点, 并且记录它的值即可,虽然这样不能避免递归的次数,但是可以空间复杂度到O(1).

AC代码

很容易写出如下代码.

private int num = 0;
private int count = 0;

public int kthSmallest(TreeNode root, int k) {
    inorder(root, k);
    return num;
}

private void inorder(TreeNode root, int k) {
    // 减枝
    if (root == null || count >= k) {
        return;
    }
    inorder(root.left, k);
    count++;
    if (k == count) {
        num = root.val;
    }
    inorder(root.right, k);
}

时间复杂是O(n),空间复杂度是O(1).

非递归解法(栈)

总所周知通过栈我们能实现二叉树的中序遍历, 非递归的遍历的好处就是我们能提前结束,而不需等到整个二叉树遍历完.

同时在遍历的时候取第k个数的值即可.

AC代码

代码如下

public int kthSmallest(TreeNode root, int k) {
    Stack<TreeNode> stack = new Stack<>();
    while (true) {
        while (root != null) {
            stack.push(root);
            root = root.left;
        }
        root = stack.pop();
        if (--k == 0) {
            return root.val;
        }
        root = root.right;
    }
}