1樓：
二叉樹擴充套件為樹(即樹的直徑)，其實是很經典的演算法。常見有兩種寫法：1樹形dp 2貪心。
列印路徑的話，與普通dp列印路徑一樣(我習慣是求出最優值再根據dp的決策遞迴列印)
下面的截圖來自紫書p281。
2樓：rsa
二叉樹上每條路徑都可以分成兩段，前半段深度遞減，後半段深度遞增。
於是我們可以列舉路徑上深度最小的點v，記l和r為v的兩個子結點，那麼前半段和後半段必然乙個在l子樹內，乙個在r子樹內，於是以v為深度最小的結點的最長路徑長度為h(l)+h(r)。
其中高度h的定義是：空二叉樹高度為0，否則高度為max+1，l,r為左右子結點。換句話說h(v)就是從結點v出發的最長的深度遞增的路徑長度。
那麼通過列舉深度最小的點v就能找到直徑（最長路徑）對應的v。分別從v的左、右子樹出發，每次往高度較大的乙個子樹走，直到走進空子樹為止，就能得到直徑的兩半段，把這兩半連同v拼起來就得到直徑的完整路徑了。
3樓：
一般做法是寫個樹上dp， 。建議自己腦補出來，很簡單。
實在補不出來的話：
對於根節點，直徑要麼經過它，要麼經過它的子樹。
對於前者（經過這個根節點），最遠點對一定在兩棵子樹裡面。那麼我們求出每棵子樹中距root最遠的點是誰，把這個距離扔進dis陣列；然後從dis陣列取出最大的點和第二大的點。
對於後者（經過它的子樹），不用管，遞迴下去，交給子樹處理。
實現是dfs，對於點x的每個子樹，記錄下到x的最遠點。取最遠和第二遠的點，這就是x所管轄的區間內的最遠點對，這倆點記為u[x]和v[x]，距離記為dis[x]；然後把最遠點回溯上去。
最後把所有的點都拎出來，看看誰的dis值最大。dis值最大的u[x]到v[x]就是一條直徑。
不過我更喜歡乙個比較小眾的辦法，非常無腦：
任選乙個點x
找到乙個距x最遠的點u
找到乙個距u最遠的點v
u-v即為樹的乙個直徑。
結合樹形dp和上述做法，可以 求出這棵樹的所有直徑。
為什麼說「滿二叉樹也是完全二叉樹」？
一名 1 先明確完全二叉樹的概念。先上圖！完全二叉樹分為樓主所說的 圖1就是了 還有一種完全二叉樹是圖2。圖2也是完全二叉樹！圖2也是完全二叉樹！圖2也是完全二叉樹！概念 完全二叉樹分為兩種，1 最後一層沒有滿，那麼最後一層的節點都得在左邊。2 最後一層滿了，那就得全滿才行，圖2。完全二叉樹就這麼個...
2021 04 11 判斷二叉樹是否是完全二叉樹？
一鯨 const completeSize node node const sl completeSize left if sl 0 return 1 const sr completeSize right if sr 0 return 1 const fl sl 1 sl const fr sr ...
delete二叉樹根節點，會一次清空二叉樹占用的記憶體嗎？
一頁書 你需要自己實現析構函式。假設你的節點定義是這樣 struct TreeNode TreeNode TreeNode if right nullptr 魚你太美 上面幾樓的答案都是錯的。其實這不就是乙個深度優先 後序遍歷訪問每乙個結點的過程嗎，只不過訪問結點的方式改成了delete而已。析構根...