# 0230. 二叉搜索樹中第K小的元素 ## 題目地址(230. 二叉搜索樹中第K小的元素) <https://leetcode-cn.com/problems/kth-smallest-element-in-a-bst/> ## 題目描述 ``` <pre class="calibre18">``` 給定一個二叉搜索樹，編寫一個函數 kthSmallest 來查找其中第 k 個最小的元素。 說明： 你可以假設 k 總是有效的，1 ≤ k ≤ 二叉搜索樹元素個數。 示例 1: 輸入: root = [3,1,4,null,2], k = 1 3 / \ 1 4 \ 2 輸出: 1 示例 2: 輸入: root = [5,3,6,2,4,null,null,1], k = 3 5 / \ 3 6 / \ 2 4 / 1 輸出: 3 進階： 如果二叉搜索樹經常被修改（插入/刪除操作）并且你需要頻繁地查找第 k 小的值，你將如何優化 kthSmallest 函數？ ``` ``` ## 前置知識 - 中序遍歷 ## 公司 - 阿里 - 騰訊 - 百度 - 字節 ## 思路 解法一： 由于‘中序遍歷一個二叉查找樹（BST）的結果是一個有序數組’ ，因此我們只需要在遍歷到第k個，返回當前元素即可。 中序遍歷相關思路請查看[binary-tree-traversal](binary-tree-traversal.html) 解法二： 聯想到二叉搜索樹的性質，root 大于左子樹，小于右子樹，如果左子樹的節點數目等于 K-1，那么 root 就是結果，否則如果左子樹節點數目小于 K-1，那么結果必然在右子樹，否則就在左子樹。 因此在搜索的時候同時返回節點數目，跟 K 做對比，就能得出結果了。 ## 關鍵點解析 - 中序遍歷 ## 代碼 解法一： JavaScript Code: ``` <pre class="calibre18">``` <span class="hljs-title">/* * @lc app=leetcode id=230 lang=javascript * * [230] Kth Smallest Element in a BST */</span> <span class="hljs-title">/** * Definition for a binary tree node. * function TreeNode(val) { * this.val = val; * this.left = this.right = null; * } */</span> <span class="hljs-title">/** * @param {TreeNode} root * @param {number} k * @return {number} */</span> <span class="hljs-keyword">var</span> kthSmallest = <span class="hljs-function"><span class="hljs-keyword">function</span>(<span class="hljs-params">root, k</span>) </span>{ <span class="hljs-keyword">const</span> stack = [root]; <span class="hljs-keyword">let</span> cur = root; <span class="hljs-keyword">let</span> i = <span class="hljs-params">0</span>; <span class="hljs-function"><span class="hljs-keyword">function</span> <span class="hljs-title">insertAllLefts</span>(<span class="hljs-params">cur</span>) </span>{ <span class="hljs-keyword">while</span>(cur && cur.left) { <span class="hljs-keyword">const</span> l = cur.left; stack.push(l); cur = l; } } insertAllLefts(cur); <span class="hljs-keyword">while</span>(cur = stack.pop()) { i++; <span class="hljs-keyword">if</span> (i === k) <span class="hljs-keyword">return</span> cur.val; <span class="hljs-keyword">const</span> r = cur.right; <span class="hljs-keyword">if</span> (r) { stack.push(r); insertAllLefts(r); } } <span class="hljs-keyword">return</span> <span class="hljs-params">-1</span>; }; ``` ``` Java Code: ``` <pre class="calibre18">``` <span class="hljs-title">/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */</span> <span class="hljs-keyword">private</span> <span class="hljs-keyword">int</span> count = <span class="hljs-params">1</span>; <span class="hljs-keyword">private</span> <span class="hljs-keyword">int</span> res; <span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-keyword">int</span> <span class="hljs-title">KthSmallest</span> <span class="hljs-params">(TreeNode root, <span class="hljs-keyword">int</span> k)</span> </span>{ inorder(root, k); <span class="hljs-keyword">return</span> res; } <span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-keyword">void</span> <span class="hljs-title">inorder</span> <span class="hljs-params">(TreeNode root, <span class="hljs-keyword">int</span> k)</span> </span>{ <span class="hljs-keyword">if</span> (root == <span class="hljs-keyword">null</span>) <span class="hljs-keyword">return</span>; inorder(root.left, k); <span class="hljs-keyword">if</span> (count++ == k) { res = root.val; <span class="hljs-keyword">return</span>; } inorder(root.right, k); } ``` ``` 解法二： JavaScript Code: ``` <pre class="calibre18">``` <span class="hljs-title">/** * Definition for a binary tree node. * function TreeNode(val) { * this.val = val; * this.left = this.right = null; * } */</span> <span class="hljs-function"><span class="hljs-keyword">function</span> <span class="hljs-title">nodeCount</span>(<span class="hljs-params">node</span>) </span>{ <span class="hljs-keyword">if</span> (node === <span class="hljs-params">null</span>) <span class="hljs-keyword">return</span> <span class="hljs-params">0</span>; <span class="hljs-keyword">const</span> l = nodeCount(node.left); <span class="hljs-keyword">const</span> r = nodeCount(node.right); <span class="hljs-keyword">return</span> <span class="hljs-params">1</span> + l + r; } <span class="hljs-title">/** * @param {TreeNode} root * @param {number} k * @return {number} */</span> <span class="hljs-keyword">var</span> kthSmallest = <span class="hljs-function"><span class="hljs-keyword">function</span>(<span class="hljs-params">root, k</span>) </span>{ <span class="hljs-keyword">const</span> c = nodeCount(root.left); <span class="hljs-keyword">if</span> (c === k - <span class="hljs-params">1</span>) <span class="hljs-keyword">return</span> root.val; <span class="hljs-keyword">else</span> <span class="hljs-keyword">if</span> (c < k - <span class="hljs-params">1</span>) <span class="hljs-keyword">return</span> kthSmallest(root.right, k - c - <span class="hljs-params">1</span>); <span class="hljs-keyword">return</span> kthSmallest(root.left, k) }; ``` ``` **復雜度分析** - 時間復雜度：O(N)O(N)O(N) - 空間復雜度：O(N)O(N)O(N) ## 擴展 這道題有一個follow up： `What if the BST is modified (insert/delete operations) often and you need to find the kth smallest frequently? How would you optimize the kthSmallest routine?` 建議大家思考一下。 大家對此有何看法，歡迎給我留言，我有時間都會一一查看回答。更多算法套路可以訪問我的 LeetCode 題解倉庫：<https://github.com/azl397985856/leetcode> 。 目前已經 37K star 啦。 大家也可以關注我的公眾號《力扣加加》帶你啃下算法這塊硬骨頭。