滿二叉樹一定是二叉樹嗎

2021-04-14：判斷二叉樹是否是滿二叉樹？

福大大 答案2021-04-14：

網上查到的答案，一般會計算樹的高度。我的答案不需要計算樹的高度，至於是否準確，不得而知。

1。左子節點滿。

2。右子節點滿。

3。左右子節點的數量相等。

採用遞迴即可。

程式碼用golang編寫。程式碼如下：

package mainimport “fmt”func main（） { head ：= &TreeNode{Val： 5} head。Left = &TreeNode{Val： 3} head。Right = &TreeNode{Val： 7} head。Left。Left = &TreeNode{Val： 2} head。Left。Right = &TreeNode{Val： 4} head。Right。Left = &TreeNode{Val： 6} head。Right。Right = &TreeNode{Val： 8} ret ：= IsFBT（head） fmt。Println（“是否是滿二叉樹：”， ret）}//Definition for a binary tree node。type TreeNode struct { Val int Left *TreeNode Right *TreeNode}type Info struct { IsFull bool Cnt int}func IsFBT（head *TreeNode） bool { return process（head）。IsFull}func process（head *TreeNode） *Info { if head == nil { return &Info{IsFull： true} } leftInfo ：= process（head。Left） //左不滿 if ！leftInfo。IsFull { return leftInfo } rightInfo ：= process（head。Right） //右不滿 if ！rightInfo。IsFull { return rightInfo } //左右不等 if leftInfo。Cnt ！= rightInfo。Cnt { return new（Info） } //透過所有考驗 return &Info{IsFull： true， Cnt： leftInfo。Cnt + rightInfo。Cnt + 1}}

執行結果如下：

***

［左神java程式碼］（https：//github。com/algorithmzuo/algorithmbasic2020/blob/master/src/class12/Code04_IsFull。java）

［評論］（https：//user。qzone。qq。com/3182319461/blog/1618354692）