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

我就是我 2023-10-04 20:50 63阅读 0赞

![format_png][]

\*\*\#\# 题目描述

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

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

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

示例 1：

![format_png 1][]

输入：root = [3,1,4,null,2], k = 1
    
    输出：1
    复制代码

示例 2：

![format_png 2][]

输入：root = [5,3,6,2,4,null,null,1], k = 3
    
    输出：3
    复制代码

提示：

*  树中的节点数为 n 。
 *  1<=�<=�<=1041<=k<=n<=104
 *  0<=����.���<=1040<=Node.val<=104

### 树的遍历 + 排序 ###

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

树的遍历可以使用 `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)；排序的复杂度为 �(�log⁡�)O(nlogn)。整体复杂度为 �(�log⁡�)O(nlogn)
 *  空间复杂度：�(�)O(n)

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

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

由于我们返回的是第 �k 小的数，因此我们可以构建一个容量为 �k 的大根堆。

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

*  大根堆元素不足 �k 个：直接将当前节点值放入大根堆；
 *  大根堆元素为 �k 个，根据堆顶元素和当前节点值的大小关系进一步分情况讨论：
    
     *  如果当前节点值元素大于堆顶元素，说明当前节点值不可能在第 �k 小的范围内，直接丢弃；
     *  如果当前节点值元素小于堆顶元素，说明当前节点值可能在第 �k 小的范围内，先 `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)；使用优先队列（堆）复杂度为 �(�log⁡�)O(nlogk)。整体复杂度为 �(�log⁡�)O(nlogk)
 *  空间复杂度：空间多少取决于 `d` 和 `q` 使用的容量，`q` 最多不超过 �k 个元素，复杂度为 �(�)O(k)，`d` 最多不超过二叉树的一层，复杂度为 �(�)O(n)。整体复杂度为 �(�+�)O(n+k)

### 中序遍历 ###

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

而我们知道，二叉搜索树的中序遍历是有序的，因此我们只需要对二叉搜索树执行中序遍历，并返回第 �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);
        }
    }
    复制代码

*  时间复杂度：由于存在对 �k 大小的剪枝，因此整个遍历顺序是从小到大进行遍历，搜索到目标值即结束。复杂度为 �(�)O(k)
 *  空间复杂度：令 ℎh 为树高，复杂度为 �(ℎ)O(h)

### 最后 ###

这是我们「刷穿 LeetCode」系列文章的第 `No.230` 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先把所有不带锁的题目刷完。

在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。

为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的仓库：[github.com/SharingSour…][github.com_SharingSour] 。

在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。

[format_png]: https://img-blog.csdnimg.cn/img_convert/b4cc700dd7a083409b6049cc3d2a8901.webp?x-oss-process=image/format,png
[230. _K]: https://link.juejin.cn/?target=https%3A%2F%2Fleetcode-cn.com%2Fproblems%2Fkth-smallest-element-in-a-bst%2Fsolution%2Fgong-shui-san-xie-yi-ti-san-jie-pai-xu-y-8uah%2F
[format_png 1]: https://img-blog.csdnimg.cn/img_convert/f7bfff2882871e345b28d5cd02af6dfe.webp?x-oss-process=image/format,png
[format_png 2]: https://img-blog.csdnimg.cn/img_convert/f2322b9465f4d6134c5140c0ceda9b43.webp?x-oss-process=image/format,png
[github.com_SharingSour]: https://link.juejin.cn/?target=https%3A%2F%2Fgithub.com%2FSharingSource%2FLogicStack-LeetCode