資訊專(zhuān)欄INFORMATION COLUMN
摘要：題目描述輸入一棵二叉樹(shù)，求該樹(shù)的深度。遞歸解法非遞歸解法原來(lái)標(biāo)識(shí)當(dāng)前層是否遍歷完畢當(dāng)前彈出元素為時(shí)，說(shuō)明一層以及遍歷完畢了，所以最后一層的彈出時(shí)不能再往隊(duì)列里面加了
題目描述
輸入一棵二叉樹(shù)，求該樹(shù)的深度。從根結(jié)點(diǎn)到葉結(jié)點(diǎn)依次經(jīng)過(guò)的結(jié)點(diǎn)（含根、葉結(jié)點(diǎn)）形成樹(shù)的一條路徑，最長(zhǎng)路徑的長(zhǎng)度為樹(shù)的深度。
遞歸解法function TreeNode(x) {
this.val = x;
this.left = null;
this.right = null;
}
function Depth(r) {
if(r === null)
return 0;
return Math.max(Depth(r.left), Depth(r.right))+1;
}
非遞歸解法
function TreeDepth(r)
{
if(r === null)
return 0;
var q = [];
var depth = 0;
q.push(r);
// null原來(lái)標(biāo)識(shí)當(dāng)前層是否遍歷完畢
q.push(null);
while(q.length !== 0){
var cur = q.shift();
// 當(dāng)前彈出元素為null時(shí)，說(shuō)明一層以及遍歷完畢了，所以depth+1
if(cur === null){
depth++;
if(q.length!==0)
// 最后一層的null彈出時(shí)不能再往隊(duì)列里面加null了
q.push(null);
}
else{
if(cur.left !== null)
q.push(cur.left);
if(cur.right !== null)
q.push(cur.right);
}
}
return depth;
}
文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請(qǐng)注明本文地址：http://m.specialneedsforspecialkids.com/yun/95634.html
摘要：大家在聊到二叉樹(shù)的時(shí)候，總會(huì)離不開(kāi)鏈表。受限線性表主要包括棧和隊(duì)列，受限表示對(duì)結(jié)點(diǎn)的操作受限制。存儲(chǔ)結(jié)構(gòu)線性表主要由順序表示或鏈?zhǔn)奖硎尽ｆ準(zhǔn)奖硎局傅氖怯靡唤M任意的存儲(chǔ)單元存儲(chǔ)線性表中的數(shù)據(jù)元素，稱(chēng)為線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。 大家在聊到二叉樹(shù)的時(shí)候，總會(huì)離不開(kāi)鏈表。這里先帶大家一起了解一些基本概念。 線性表 概念 線性表是最基本、最簡(jiǎn)單、也是最常用的一種數(shù)據(jù)結(jié)構(gòu)。 線性表中數(shù)據(jù)元素之間的關(guān)...
摘要：寫(xiě)在最前面導(dǎo)師貪腐出逃美國(guó)，兩年未歸，可憐了我。拿了小米和美團(tuán)的，要被延期，失效，工作重新找。把準(zhǔn)備過(guò)程紀(jì)錄下來(lái)，共勉。 寫(xiě)在最前面 導(dǎo)師貪腐出逃美國(guó)，兩年未歸，可憐了我。拿了小米和美團(tuán)的offer，要被延期，offer失效，工作重新找。把準(zhǔn)備過(guò)程紀(jì)錄下來(lái)，共勉。 二叉樹(shù)的基礎(chǔ) 結(jié)點(diǎn)定義 public class TreeNode{ int val; TreeNode ...
摘要：題目描述操作給定的二叉樹(shù)，將其變翻轉(zhuǎn)為源二叉樹(shù)的鏡像。輸入描述解題思路遞歸版本首先，對(duì)數(shù)據(jù)結(jié)構(gòu)比較了解的話會(huì)想到用遞歸來(lái)解決。所謂遞歸，在計(jì)算機(jī)科學(xué)中是指一種通過(guò)重復(fù)將問(wèn)題分解為同類(lèi)的子問(wèn)題而解決問(wèn)題的方法來(lái)自維基百科。 題目描述 操作給定的二叉樹(shù)，將其變翻轉(zhuǎn)為源二叉樹(shù)的鏡像。 輸入描述: 1 1 / ...
摘要：后面也寫(xiě)了幾種常見(jiàn)的排序算法，并用快排求第大值，另外如果之前版的作者看到的話可以留言，我會(huì)標(biāo)明文章引用。 之前實(shí)習(xí)筆試的時(shí)候刷題一直用的java，也參考某篇文章寫(xiě)過(guò)java版的二叉樹(shù)常見(jiàn)算法，因?yàn)轳R上要轉(zhuǎn)正面試了，這幾天都在準(zhǔn)備面試，就把之前的翻出來(lái)用javascript重新寫(xiě)了一遍，二叉樹(shù)基本都是遞歸處理的，也比較簡(jiǎn)單，就當(dāng)做熱身。后面也寫(xiě)了幾種常見(jiàn)的排序算法，并用快排求第K大值，另...
閱讀 2150·2023-04-26 03:06
閱讀 3603·2023-04-26 01:51
閱讀 2103·2021-11-24 09:38
閱讀 2473·2021-11-17 17:00
閱讀 2342·2021-09-28 09:36
閱讀 951·2021-09-24 09:47
閱讀 2595·2019-08-30 15:54
閱讀 1567·2019-08-30 15:44
