1.二叉樹(shù)的最大深度
- 什么是二叉樹(shù)的深度?
根節(jié)點(diǎn)到最遠(yuǎn)葉子節(jié)點(diǎn)的最長(zhǎng)路徑上的節(jié)點(diǎn)數(shù)-
什么是葉子節(jié)點(diǎn)?
沒(méi)有子節(jié)點(diǎn)的節(jié)點(diǎn)(左右孩子都為空才行)
image.png
-
用遞歸法,三要素:
- 確定參數(shù)和返回值
參數(shù)就root,返回深度
2.確定終止條件
如果左右節(jié)點(diǎn)都沒(méi)有就返回
如果空節(jié)點(diǎn)就返回
3.確定單層遞歸邏輯:
先求左子樹(shù)深度,再求右子樹(shù)深度,取最大再+1(中間節(jié)點(diǎn))
2.n叉樹(shù)的最大深度
n叉樹(shù)沒(méi)有l(wèi)eft,right,只有childen,所以要用for遍歷.
3.二叉樹(shù)的最小深度
- 前序遍歷和后序遍歷的區(qū)別
前序遍歷用來(lái)求深度,后序遍歷用來(lái)求高度.
- 二叉樹(shù)節(jié)點(diǎn)的深度：指從根節(jié)點(diǎn)到該節(jié)點(diǎn)的最長(zhǎng)簡(jiǎn)單路徑邊的條數(shù)或者節(jié)點(diǎn)數(shù)（取決于深度從0開(kāi)始還是從1開(kāi)始）
- 二叉樹(shù)節(jié)點(diǎn)的高度：指從該節(jié)點(diǎn)到葉子節(jié)點(diǎn)的最長(zhǎng)簡(jiǎn)單路徑邊的條數(shù)或者節(jié)點(diǎn)數(shù)（取決于高度從0開(kāi)始還是從1開(kāi)始）
二叉樹(shù)的最小深度?
最小深度是從根節(jié)點(diǎn)到最近葉子節(jié)點(diǎn)的最短路徑上的節(jié)點(diǎn)數(shù)量。，注意是葉子節(jié)點(diǎn)。-
和求最大深度的區(qū)別
主要差別在于處理左右孩子不為空的邏輯
在這種情況下,如果求最小深度,A的右節(jié)點(diǎn)是不存在的,所以如果不特別考慮只有一個(gè)節(jié)點(diǎn)的情況的話,這個(gè)樹(shù)的最小深度成了1了,也就是A自己,但是這明顯不對(duì).
而最大深度不用考慮的原因是,就算右節(jié)點(diǎn)不存在,影響最大深度的從來(lái)都是存在的節(jié)點(diǎn), 進(jìn)入遞歸的返回值設(shè)置的時(shí)候要
return 1+minDepth()而不是return minDepth()
4.完全二叉樹(shù)的節(jié)點(diǎn)個(gè)數(shù)
解法一:看作普通二叉樹(shù)做
解法2 用完全二叉樹(shù)的性質(zhì)做,
滿二叉樹(shù)某深度的節(jié)點(diǎn)個(gè)數(shù)應(yīng)該是Math.pow(2,n)+1,而且滿二叉樹(shù)的話,全部左邊的深度應(yīng)該等于全部右邊的深度,如果不是滿二叉樹(shù),那就左邊的個(gè)數(shù)加上右邊的個(gè)數(shù)+1
