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