【面试高频题】难度 1/5，简单二叉树寻值问题

宫水三叶的刷题日记

发布于 2023-02-27 10:51:48

3710

发布于 2023-02-27 10:51:48

文章被收录于专栏：宫水三叶的刷题日记

题目描述

这是 LeetCode 上的 「230. 二叉搜索树中第K小的元素」 ，难度为 「中等」。

Tag : 「二叉树」、「中序遍历」、「树的搜索」

给定一个二叉搜索树的根节点 root，和一个整数 k ，请你设计一个算法查找其中第 k 个最小元素（从

开始计数）。

示例 1：

输入：root = [3,1,4,null,2], k = 1

输出：1

示例 2：

输入：root = [5,3,6,2,4,null,null,1], k = 3

输出：3

提示：

树中的节点数为 n 。

1 <= k <= n <= 10^4

0 <= Node.val <= 10^4

树的遍历 + 排序

朴素的做法是先对二叉树进行一次完整遍历，将所有节点存入列表中，最后对列表排序后返回目标值。

树的遍历可以使用 DFS 或 BFS。

代码：

class Solution {
    List<Integer> list = new ArrayList<>();
    public int kthSmallest(TreeNode root, int k) {
        dfs(root);
        Collections.sort(list);
        return list.get(k - 1);
    }
    void dfs(TreeNode root) {
        if (root == null) return ;
        list.add(root.val);
        dfs(root.left);
        dfs(root.right);
    }
}

时间复杂度：树的遍历时间复杂度为

O(n)

；排序的复杂度为

O(n\log{n})

。整体复杂度为

O(n\log{n})

空间复杂度：

O(n)

树的遍历 + 优先队列（堆）

相比于先直接拿到所有节点再排序的解法一，另外一种做法是使用「优先队列（堆）」来做。

由于我们返回的是第

小的数，因此我们可以构建一个容量为

的大根堆。

根据大根堆的元素个数和当前节点与堆顶元素的关系来分情况讨论：

大根堆元素不足

个：直接将当前节点值放入大根堆；

大根堆元素为

个，根据堆顶元素和当前节点值的大小关系进一步分情况讨论：

如果当前节点值元素大于堆顶元素，说明当前节点值不可能在第

小的范围内，直接丢弃；

如果当前节点值元素小于堆顶元素，说明当前节点值可能在第

小的范围内，先 poll 一个再 add 进去。

树的遍历可以使用 DFS 或 BFS。

代码：

class Solution {
    public int kthSmallest(TreeNode root, int k) {
        PriorityQueue<Integer> q = new PriorityQueue<>((a,b)->b-a);
        Deque<TreeNode> d = new ArrayDeque<>();
        d.addLast(root);
        while (!d.isEmpty()) {
            TreeNode node = d.pollFirst();
            if (q.size() < k) {
                q.add(node.val);
            } else if (q.peek() > node.val) {
                q.poll();
                q.add(node.val);
            }
            if (node.left != null) d.addLast(node.left);
            if (node.right != null) d.addLast(node.right);
        }
        return q.peek();
    }
}

时间复杂度：树的遍历时间复杂度为

O(n)

；使用优先队列（堆）复杂度为

O(n\log{k})

。整体复杂度为

O(n\log{k})

空间复杂度：空间多少取决于 d 和 q 使用的容量，q 最多不超过

个元素，复杂度为

O(k)

，d 最多不超过二叉树的一层，复杂度为

O(n)

。整体复杂度为

O(n + k)

中序遍历

上述两种节点，都没有利用该树为二叉搜索树的特性。

而我们知道，二叉搜索树的中序遍历是有序的，因此我们只需要对二叉搜索树执行中序遍历，并返回第

小的值即可。

中序遍历有「迭代」和「递归」两种写法。

代码：

class Solution {
    public int kthSmallest(TreeNode root, int k) {
        Deque<TreeNode> d = new ArrayDeque<>();
        while (root != null || !d.isEmpty()) {
            while (root != null) {
                d.addLast(root);
                root = root.left;
            }
            root = d.pollLast();
            if (--k == 0) return root.val;
            root = root.right;
        }
        return -1; // never
    }
}

class Solution {
    int k, ans;
    public int kthSmallest(TreeNode root, int _k) {
        k = _k;
        dfs(root);
        return ans;
    }
    void dfs(TreeNode root) {
        if (root == null || k <= 0) return ;
        dfs(root.left);
        if (--k == 0) ans = root.val;
        dfs(root.right);
    }
}