資訊專欄INFORMATION COLUMN
摘要：題目描述給定一棵二叉搜索樹，請(qǐng)找出其中的第小的結(jié)點(diǎn)。例如，，，，，，，中，按結(jié)點(diǎn)數(shù)值從小到大順序第三小結(jié)點(diǎn)的值為。分析二叉搜索樹的特點(diǎn)就是對(duì)于某個(gè)點(diǎn)來說，左子樹上的點(diǎn)小于該點(diǎn)，右子樹上的點(diǎn)大于該點(diǎn)。
題目描述
給定一棵二叉搜索樹，請(qǐng)找出其中的第k小的結(jié)點(diǎn)。例如， （5，3，7，2，4，6，8） 中，按結(jié)點(diǎn)數(shù)值從小到大順序第三小結(jié)點(diǎn)的值為4。
分析二叉搜索樹的特點(diǎn)就是對(duì)于某個(gè)點(diǎn)來說，左子樹上的點(diǎn)小于該點(diǎn)，右子樹上的點(diǎn)大于該點(diǎn)。所以按照中序遍歷的方法得到的序列即是從小到大的序列。
代碼/* function TreeNode(x) {
this.val = x;
this.left = null;
this.right = null;
} */
function KthNode(r, k)
{
if(r === null)
return null;
var res = [];
var s = [];
var cur = r;
while(cur !== null || s.length !== 0) {
if(cur !== null){
s.push(cur);
cur = cur.left;
}else{
cur = s.pop();
res.push(cur);
if(res.length === k)
return res.pop();
cur = cur.right;
}
}
return null;
}
文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請(qǐng)注明本文地址：http://www.ezyhdfw.cn/yun/96230.html
文章目錄 一、題目1、題目描述2、基礎(chǔ)框架3、原題鏈接 二、解題報(bào)告1、思路分析2、時(shí)間復(fù)雜度3、代碼詳解 三、本題小知識(shí)四、加群須知 一、題目 1、題目描述 ??給你一棵二叉搜索樹，請(qǐng)按 中序遍歷 將其重新排列為一棵遞增順序搜索樹，使樹中最左邊的節(jié)點(diǎn)成為樹的根節(jié)點(diǎn)，并且每個(gè)節(jié)點(diǎn)沒有左子節(jié)點(diǎn)，只有一個(gè)右子節(jié)點(diǎn)。??樣例輸入： [5,3,6,2,4,null,8,1,null,null,nu...
摘要：在二叉查找樹上執(zhí)行基本操作的時(shí)間與樹的高度成正比。不同的二叉查找樹可以表示同一組值。紅黑樹樹二叉查找樹，紅黑樹，樹紅黑樹 雖是讀書筆記，但是如轉(zhuǎn)載請(qǐng)注明出處 http://segmentfault.com/blog/exploring/ .. 拒絕伸手復(fù)制黨 關(guān)于二叉樹的基本知識(shí)，可以參見：Java 實(shí)現(xiàn)基本數(shù)據(jù)結(jié)構(gòu) 2(樹) 以下是算法導(dǎo)論第十二章的學(xué)習(xí)筆記 二叉查找樹 BS...
摘要：上一篇數(shù)據(jù)結(jié)構(gòu)與算法集合字典一遞歸學(xué)習(xí)樹離不開遞歸。先序遍歷的一種應(yīng)用是打印一個(gè)結(jié)構(gòu)化的文檔下面的圖描繪了先序遍歷方法的訪問路徑后序遍歷后序遍歷則是先訪問節(jié)點(diǎn)的后代節(jié)點(diǎn)，再訪問節(jié)點(diǎn)本身。 上一篇：JS數(shù)據(jù)結(jié)構(gòu)與算法_集合&字典 一、遞歸 學(xué)習(xí)樹離不開遞歸。 1.1 介紹 遞歸是一種解決問題的方法，它解決問題的各個(gè)小部分，直到解決最初的大問題。遞歸通常涉及函數(shù)調(diào)用自身。 通俗的解釋：年級(jí)...
摘要：同樣結(jié)點(diǎn)樹的二叉樹，完全二叉樹的深度最小。二叉樹每個(gè)結(jié)點(diǎn)最多有兩個(gè)孩子，所以為它設(shè)計(jì)一個(gè)數(shù)據(jù)域和兩個(gè)指針域是比較自然的想法，我們稱這樣的鏈表叫做二叉鏈表。 二叉樹的概念 二叉樹（Binary Tree）是n（n>=0）個(gè)結(jié)點(diǎn)的有限集合，該集合或者為空集（空二叉樹），或者由一個(gè)根結(jié)點(diǎn)和兩棵互不相交的、分別稱為根結(jié)點(diǎn)的左子樹和右子樹的二叉樹組成。 showImg(https://seg...
閱讀 862·2023-04-26 01:42
閱讀 3363·2021-11-22 11:56
閱讀 2568·2021-10-08 10:04
閱讀 1042·2021-09-24 10:37
閱讀 3295·2019-08-30 15:52
閱讀 2010·2019-08-29 13:44
閱讀 638·2019-08-28 17:51
閱讀 2299·2019-08-26 18:26
