1"use strict";(self.webpackChunkjjbook=self.webpackChunkjjbook||[]).push([[6099],{3905:(e,t,n)=>{n.d(t,{Zo:()=>s,kt:()=>f});var r=n(67294);function o(e,t,n){return t in e?Object.defineProperty(e,t,{value:n,enumerable:!0,configurable:!0,writable:!0}):e[t]=n,e}function a(e,t){var n=Object.keys(e);if(Object.getOwnPropertySymbols){var r=Object.getOwnPropertySymbols(e);t&&(r=r.filter((function(t){return Object.getOwnPropertyDescriptor(e,t).enumerable}))),n.push.apply(n,r)}return n}function l(e){for(var t=1;t<arguments.length;t++){var n=null!=arguments[t]?arguments[t]:{};t%2?a(Object(n),!0).forEach((function(t){o(e,t,n[t])})):Object.getOwnPropertyDescriptors?Object.defineProperties(e,Object.getOwnPropertyDescriptors(n)):a(Object(n)).forEach((function(t){Object.defineProperty(e,t,Object.getOwnPropertyDescriptor(n,t))}))}return e}function i(e,t){if(null==e)return{};var n,r,o=function(e,t){if(null==e)return{};var n,r,o={},a=Object.keys(e);for(r=0;r<a.length;r++)n=a[r],t.indexOf(n)>=0||(o[n]=e[n]);return o}(e,t);if(Object.getOwnPropertySymbols){var a=Object.getOwnPropertySymbols(e);for(r=0;r<a.length;r++)n=a[r],t.indexOf(n)>=0||Object.prototype.propertyIsEnumerable.call(e,n)&&(o[n]=e[n])}return o}var u=r.createContext({}),p=function(e){var t=r.useContext(u),n=t;return e&&(n="function"==typeof e?e(t):l(l({},t),e)),n},s=function(e){var t=p(e.components);return r.createElement(u.Provider,{value:t},e.children)},c="mdxType",k={inlineCode:"code",wrapper:function(e){var t=e.children;return r.createElement(r.Fragment,{},t)}},d=r.forwardRef((function(e,t){var n=e.components,o=e.mdxType,a=e.originalType,u=e.parentName,s=i(e,["components","mdxType","originalType","parentName"]),c=p(n),d=o,f=c["".concat(u,".").concat(d)]||c[d]||k[d]||a;return n?r.createElement(f,l(l({ref:t},s),{},{components:n})):r.createElement(f,l({ref:t},s))}));function f(e,t){var n=arguments,o=t&&t.mdxType;if("string"==typeof e||o){var a=n.length,l=new Array(a);l[0]=d;var i={};for(var u in t)hasOwnProperty.call(t,u)&&(i[u]=t[u]);i.originalType=e,i[c]="string"==typeof e?e:o,l[1]=i;for(var p=2;p<a;p++)l[p]=n[p];return r.createElement.apply(null,l)}return r.createElement.apply(null,n)}d.displayName="MDXCreateElement"},3581:(e,t,n)=>{n.r(t),n.d(t,{assets:()=>u,contentTitle:()=>l,default:()=>k,frontMatter:()=>a,metadata:()=>i,toc:()=>p});var r=n(87462),o=(n(67294),n(3905));const a={sidebar_label:"\u7b97\u6cd5\uff1a\u4e8c\u53c9\u641c\u7d22\u6811\u7684\u7b2c k \u4e2a\u7ed3\u70b9",sidebar_position:11},l="\u4e8c\u53c9\u641c\u7d22\u6811\u7684\u7b2c k \u5927\u7684\u8282\u70b9",i={unversionedId:"book3/algorithm-binary-tree-k",id:"book3/algorithm-binary-tree-k",title:"\u4e8c\u53c9\u641c\u7d22\u6811\u7684\u7b2c k \u5927\u7684\u8282\u70b9",description:"\u9898\u76ee\u63cf\u8ff0",source:"@site/docs/book3/algorithm-binary-tree-k.md",sourceDirName:"book3",slug:"/book3/algorithm-binary-tree-k",permalink:"/awesome-interview/book3/algorithm-binary-tree-k",draft:!1,tags:[],version:"current",sidebarPosition:11,frontMatter:{sidebar_label:"\u7b97\u6cd5\uff1a\u4e8c\u53c9\u641c\u7d22\u6811\u7684\u7b2c k \u4e2a\u7ed3\u70b9",sidebar_position:11},sidebar:"tutorialSidebar",previous:{title:"\u7f16\u7801\uff1a\u5c06\u5217\u8868\u8fd8\u539f\u4e3a\u6811\u72b6\u7ed3\u6784",permalink:"/awesome-interview/book3/coding-arr-to-tree"},next:{title:"\u7efc\u5408\uff1a\u5982\u4f55\u51cf\u5c11\u767d\u5c4f\u7684\u65f6\u95f4",permalink:"/awesome-interview/book3/topic-white-screen-optimization"}},u={},p=[{value:"\u9898\u76ee\u63cf\u8ff0",id:"\u9898\u76ee\u63cf\u8ff0",level:2},{value:"\u89e3\u9898\u57fa\u672c\u77e5\u8bc6",id:"\u89e3\u9898\u57fa\u672c\u77e5\u8bc6",level:2},{value:"\u89e3\u6cd5\u4e00\uff1a \u9012\u5f52",id:"\u89e3\u6cd5\u4e00-\u9012\u5f52",level:2},{value:"\u590d\u6742\u5ea6\u5206\u6790\uff1a",id:"\u590d\u6742\u5ea6\u5206\u6790",level:3},{value:"\u89e3\u6cd5\u4e8c\uff1a \u8fed\u4ee3",id:"\u89e3\u6cd5\u4e8c-\u8fed\u4ee3",level:2},{value:"\u53c2\u8003\u8d44\u6599",id:"\u53c2\u8003\u8d44\u6599",level:3}],s={toc:p},c="wrapper";function k(e){let{components:t,...n}=e;return(0,o.kt)(c,(0,r.Z)({},s,n,{components:t,mdxType:"MDXLayout"}),(0,o.kt)("h1",{id:"\u4e8c\u53c9\u641c\u7d22\u6811\u7684\u7b2c-k-\u5927\u7684\u8282\u70b9"},"\u4e8c\u53c9\u641c\u7d22\u6811\u7684\u7b2c k \u5927\u7684\u8282\u70b9"),(0,o.kt)("h2",{id:"\u9898\u76ee\u63cf\u8ff0"},"\u9898\u76ee\u63cf\u8ff0"),(0,o.kt)("p",null,"\u7ed9\u5b9a\u4e00\u68f5\u4e8c\u53c9\u641c\u7d22\u6811\uff0c\u8bf7\u627e\u51fa\u5176\u4e2d\u7b2c k \u5927\u7684\u8282\u70b9\u3002"),(0,o.kt)("p",null,"\u793a\u4f8b 1\uff1a"),(0,o.kt)("pre",null,(0,o.kt)("code",{parentName:"pre"},"\u8f93\u5165: root = [3,1,4,null,2], k = 1\n 3\n / \\\n 1 4\n \\\n 2\n\u8f93\u51fa: 4\n")),(0,o.kt)("p",null,"\u793a\u4f8b 2\uff1a"),(0,o.kt)("pre",null,(0,o.kt)("code",{parentName:"pre"},"\u8f93\u5165: root = [5,3,6,2,4,null,null,1], k = 3\n 5\n / \\\n 3 6\n / \\\n 2 4\n /\n 1\n\u8f93\u51fa: 4\n")),(0,o.kt)("h2",{id:"\u89e3\u9898\u57fa\u672c\u77e5\u8bc6"},"\u89e3\u9898\u57fa\u672c\u77e5\u8bc6"),(0,o.kt)("p",null,"\u4e8c\u53c9\u641c\u7d22\u6811\uff08Binary Search Tree\uff09\u53c8\u540d\u4e8c\u53c9\u67e5\u627e\u
16811\u3001\u4e8c\u53c9\u6392\u5e8f\u6811\u3002\u5b83\u662f\u4e00\u68f5\u7a7a\u6811\uff0c\u6216\u8005\u662f\u5177\u6709\u4e0b\u5217\u6027\u8d28\u7684\u4e8c\u53c9\u6811\uff1a \u82e5\u5b83\u7684\u5de6\u5b50\u6811\u4e0d\u7a7a\uff0c\u5219\u5de6\u5b50\u6811\u4e0a\u6240\u6709\u7ed3\u70b9\u7684\u503c\u5747\u5c0f\u4e8e\u5b83\u7684\u6839\u7ed3\u70b9\u7684\u503c\uff1b \u82e5\u5b83\u7684\u53f3\u5b50\u6811\u4e0d\u7a7a\uff0c\u5219\u53f3\u5b50\u6811\u4e0a\u6240\u6709\u7ed3\u70b9\u7684\u503c\u5747\u5927\u4e8e\u5b83\u7684\u6839\u7ed3\u70b9\u7684\u503c\uff1b \u5b83\u7684\u5de6\u3001\u53f3\u5b50\u6811\u4e5f\u5206\u522b\u4e3a\u4e8c\u53c9\u6392\u5e8f\u6811\u3002"),(0,o.kt)("h2",{id:"\u89e3\u6cd5\u4e00-\u9012\u5f52"},"\u89e3\u6cd5\u4e00\uff1a \u9012\u5f52"),(0,o.kt)("p",null,(0,o.kt)("a",{parentName:"p",href:"https://codesandbox.io/s/erchasousuoshudedi-k-dadejiedian-vfpbh?file=/index.html"},"\u5728\u7ebf\u94fe\u63a5")),(0,o.kt)("p",null,"\u5229\u7528\u4e8c\u53c9\u641c\u7d22\u6811\u7684\u7279\u6027\u8fdb\u884c\u4e2d\u5e8f\u904d\u5386\u3002\u5148\u904d\u5386\u5de6\u8282\u70b9\uff0c\u7136\u540e\u6839\u8282\u70b9\uff0c\u6700\u540e\u904d\u5386\u53f3\u8282\u70b9\uff0c\u5f97\u5230\u7684\u662f\u4e00\u4e2a\u9012\u589e\u5e8f\u5217\uff0c\u90a3\u4e48\u5e8f\u5217\u7684\u5012\u5e8f\u4e3a\u9012\u51cf\u5e8f\u5217\u3002\u56e0\u6b64\u8fd9\u9053\u9898\u6211\u4eec\u53ef\u4ee5\u8f6c\u53d8\u4e3a\u6c42\u4e8c\u53c9\u641c\u7d22\u6811\u4e2d\u5e8f\u904d\u5386\u5012\u5e8f\u7684\u7b2c k \u4e2a\u6570\u3002"),(0,o.kt)("p",null,(0,o.kt)("img",{parentName:"p",src:"https://user-images.githubusercontent.com/15681693/130164388-85e96093-9336-4174-b139-59e83d972a20.png",alt:"\u89e3\u6cd5\u56fe\u793a"})),(0,o.kt)("pre",null,(0,o.kt)("code",{parentName:"pre",className:"language-javascript"},"/**\n * Definition for a binary tree node.\n * function TreeNode(val) {\n * this.val = val;\n * this.left = this.right = null;\n * }\n */\n/**\n * @param {TreeNode} root\n * @param {number} k\n * @return {number}\n */\nconst kthLargest = (root, k) => {\n let res = null; // \u521d\u59cb\u5316\u8fd4\u56de\u503c\n // \u56e0\u4e3a\u9700\u8981\u5012\u5e8f\u7b2c k \u4e2a\uff0c\u6240\u4ee5\u5904\u7406\u662f\u53f3\u8282\u70b9\uff0c\u6839\u8282\u70b9\uff0c\u7136\u540e\u5de6\u8282\u70b9\n const dfs = (root) => {\n if (!root) return; // \u5982\u679c\u5f53\u524d\u8282\u70b9\u4e3a null\uff0c\u672c\u8f6e\u5904\u7406\u7ed3\u675f\n dfs(root.right); // \u5f00\u59cb\u5904\u7406\u53f3\u8282\u70b9\n if (k === 0) return; // k \u503c \u4e3a 0\uff0c\u4ee3\u8868\u5df2\u7ecf\u5904\u7406\u7684\u8282\u70b9\u8d85\u8fc7\u76ee\u6807\u8282\u70b9\uff0c\u672c\u8f6e\u5904\u7406\u7ed3\u675f\n if (--k === 0) {\n // \u5f53 k \u503c \u51cf 1 \u4e3a 0\uff0c\u8868\u793a\u5df2\u7ecf\u5230\u4e86\u6211\u4eec\u60f3\u8981\u7684 k \u5927 \u8282\u70b9\uff0c\u4fdd\u5b58\u5f53\u524d\u503c\n res = root.val;\n }\n dfs(root.left); // \u5904\u7406\u5de6\u8282\u70b9\n };\n dfs(root); // \u4ece\u521d\u59cb\u5316\u8282\u70b9\u5f00\u59cb\u5904\u7406\n return res;\n};\n")),(0,o.kt)("h3",{id:"\u590d\u6742\u5ea6\u5206\u6790"},"\u590d\u6742\u5ea6\u5206\u6790\uff1a"),(0,o.kt)("ul",null,(0,o.kt)("li",{parentName:"ul"},"\u65f6\u95f4\u590d\u6742\u5ea6 O(N)\uff1a\u65e0\u8bba k \u7684\u503c\u5927\u5c0f\uff0c\u9012\u5f52\u6df1\u5ea6\u90fd\u4e3a N\uff0c\u5360\u7528 O(N) \u65f6\u95f4\u3002"),(0,o.kt)("li",{parentName:"ul"},"\u7a7a\u95f4\u590d\u6742\u5ea6 O(N)\uff1a\u65e0\u8bba k \u7684\u503c\u5927\u5c0f\uff0c\u9012\u5f52\u6df1\u5ea6\u90fd\u4e3a N\uff0c\u5360\u7528 O(N) \u7a7a\u95f4\u3002")),(0,o.kt)("h2",{id:"\u89e3\u6cd5\u4e8c-\u8fed\u4ee3"},"\u89e3\u6cd5\u4e8c\uff1a \u8fed\u4ee3"),(0,o.kt)("p",null,(0,o.kt)("a",{parentName:"p",href:"https://codesandbox.io/s/hzfe-suan-fa-er-cha-sou-suo-shu-de-di-k-da-de-jie-dian-die-dai-kq565?file=/index.html"},"\u5728\u7ebf\u94fe\u63a5")),(0,o.kt)("p",null,"\u601d\u8def\u8fd8\u662f\u4e8c\u53c9\u6811\u7684\u4e2d\u5e8f\u904d\u5386\uff0c\u5229\u7528\u6808\u7684\u65b9\u5f0f\u8fdb\u884c\u904d\u5386\u3002"),(0,o.kt)("p",null,(0,o.kt)("img",{parentName:"p",src:"https://user-images.githubusercontent.com/15681693/137573367-0855a00c-7406-4837-86d4-38d73f9c7bb7.png",alt:"\u89e3\u6cd5\u56fe\u793a"})),(0,o.kt)("pre",null,(0,o.kt)("code",{parentName:"pre",className:"language-javascript"},"/**\n * Definition for a binary tree node.\n * function TreeNode(val) {\n * this.val = val;\n * this.left = this.right = null;\n * }\n */\n/**\n * @param {TreeNode} root\n * @param {number} k\n * @return {number}\n */\nvar kthLargest = function (root, k) {\n if (!root) return 0;\n // \u58f0\u660e\u50a8\u5b58\u6808\n const stack = [];\n // \u5224\u65ad\u5f53\u524d\u6808\u5426\u6709\u8282\u70b9\u548c\u5f53\u524d\u904d\u5386\u8282\u70b9\u4f4d\u7f6e\n while (stack.length || root) {\n while (root) {\n // \u5f80\u6808\u9
11cc\u6dfb\u52a0\u5f53\u524d\u8282\u70b9\uff0c\u540c\u65f6\u5207\u6362\u4e3a\u53f3\u8282\u70b9\u5904\u7406\n stack.push(root);\n root = root.right;\n }\n // \u53d6\u51fa\u5f53\u524d\u6808\u9876\u5143\u7d20\uff0c\u6839\u636e\u6dfb\u52a0\u7684\u987a\u5e8f\uff0c\u5f53\u524d\u5143\u7d20\u662f\u6808\u5185\u6700\u5927\u7684\n const cur = stack.pop();\n k--;\n if (k === 0) return cur.val;\n // \u5207\u6362\u4e3a\u5de6\u8282\u70b9\u5904\u7406\n root = cur.left;\n }\n return 0;\n};\n")),(0,o.kt)("ul",null,(0,o.kt)("li",{parentName:"ul"},"\u65f6\u95f4\u590d\u6742\u5ea6 O(N)\uff1a\u9700\u8981\u904d\u5386\u6574\u68f5\u6811\u4e00\u6b21\uff0c\u590d\u6742\u5ea6\u4e3a O(N)"),(0,o.kt)("li",{parentName:"ul"},"\u7a7a\u95f4\u590d\u6742\u5ea6 O(N)\uff1a\u9700\u8981\u989d\u5916\u7a7a\u95f4\u6808\u8fdb\u884c\u50a8\u5b58\u6811\uff0c\u590d\u6742\u5ea6\u4e3a O(N)")),(0,o.kt)("h3",{id:"\u53c2\u8003\u8d44\u6599"},"\u53c2\u8003\u8d44\u6599"),(0,o.kt)("ol",null,(0,o.kt)("li",{parentName:"ol"},(0,o.kt)("a",{parentName:"li",href:"https://book.douban.com/subject/6966465/"},"\u5251\u6307 offer"))))}k.isMDXComponent=!0}}]);
Line numbers count LF bytes from the start of the resource, as the search results do. Vendor segments are library code the classifier recognised; they are stored but not indexed. Bytes are shown as Latin1 characters, one per byte.