<ruby id="bdb3f"></ruby>

    <p id="bdb3f"><cite id="bdb3f"></cite></p>

      <p id="bdb3f"><cite id="bdb3f"><th id="bdb3f"></th></cite></p><p id="bdb3f"></p>
        <p id="bdb3f"><cite id="bdb3f"></cite></p>

          <pre id="bdb3f"></pre>
          <pre id="bdb3f"><del id="bdb3f"><thead id="bdb3f"></thead></del></pre>

          <ruby id="bdb3f"><mark id="bdb3f"></mark></ruby><ruby id="bdb3f"></ruby>
          <pre id="bdb3f"><pre id="bdb3f"><mark id="bdb3f"></mark></pre></pre><output id="bdb3f"></output><p id="bdb3f"></p><p id="bdb3f"></p>

          <pre id="bdb3f"><del id="bdb3f"><progress id="bdb3f"></progress></del></pre>

                <ruby id="bdb3f"></ruby>

                ??碼云GVP開源項目 12k star Uniapp+ElementUI 功能強大 支持多語言、二開方便! 廣告
                # 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 啦。 大家也可以關注我的公眾號《力扣加加》帶你啃下算法這塊硬骨頭。 ![](https://img.kancloud.cn/cf/0f/cf0fc0dd21e94b443dd8bca6cc15b34b_900x500.jpg)
                  <ruby id="bdb3f"></ruby>

                  <p id="bdb3f"><cite id="bdb3f"></cite></p>

                    <p id="bdb3f"><cite id="bdb3f"><th id="bdb3f"></th></cite></p><p id="bdb3f"></p>
                      <p id="bdb3f"><cite id="bdb3f"></cite></p>

                        <pre id="bdb3f"></pre>
                        <pre id="bdb3f"><del id="bdb3f"><thead id="bdb3f"></thead></del></pre>

                        <ruby id="bdb3f"><mark id="bdb3f"></mark></ruby><ruby id="bdb3f"></ruby>
                        <pre id="bdb3f"><pre id="bdb3f"><mark id="bdb3f"></mark></pre></pre><output id="bdb3f"></output><p id="bdb3f"></p><p id="bdb3f"></p>

                        <pre id="bdb3f"><del id="bdb3f"><progress id="bdb3f"></progress></del></pre>

                              <ruby id="bdb3f"></ruby>

                              哎呀哎呀视频在线观看