當給定一個由鄰接表表示的無向圖 G 時，如何使用 DFS 來查看該圖是否是完美二叉樹？
我已經能夠識別邊緣情況：例如使用這樣一個事實，即對于深度 D，您需要 2^n-1 個節點，您可以使用對數計算出最大深度，如果這不是完整的，那么您知道您沒有'沒有完美的樹，但我想不出使用鄰接表和 DFS 進行測驗的有效方法。
uj5u.com熱心網友回復：
在具有 ?? 節點的非空完美二叉樹中，我們具有以下屬性：
- 節點數??是2的冪小1，即?=log 2 (?? 1)是整數。??=2 ? ?1
- 邊數為 ???1
- 沒有超過 3 個鄰居的節點。
- 當 ?? > 1 時，（只有）一個節點正好有 2 個鄰居：它是根。
- 當?? > 1 時，樹的葉子只有一個鄰居：它們有 2 ?-1個。
- 根和任何葉子之間的距離是 ??1。
這些屬性可以一個接一個地檢查。一旦確定了根，就可以執行遍歷來檢查距離屬性。使用 DFS 或 BFS。
uj5u.com熱心網友回復：
如果圖為空，或只有一個頂點，則回傳 true。
否則，檢查以確保圖形是連通的和非回圈的。
那么，如果它是一棵完美二叉樹，那么必須只有一個度數為 2 的頂點。那就是根。讓a和b成為它的兩個孩子。然后：
let depthA = depthIfPerfect(a, root);
let depthB = depthIfPerfect(b, root);
return depthA == depthB && depthA >=0
在哪里：
depthIfPerfect(node, parent):
if degree(node) == 1:
return 1;
if degree(node) != 3:
return -1; //not perfect
let a and b be the neighbors that aren't parent
let depthA = depthIfPerfect(a, node);
let depthB = depthIfPerfect(b, node);
if (depthA != depthB || depthA < 0):
return -1: //not perfect
return depthA 1;
如果您愿意，您可以將連通性和非回圈性檢查混合到此遍歷中。
轉載請註明出處，本文鏈接：https://www.uj5u.com/yidong/362051.html
下一篇：是否可以通過小塊計算哈希？