漫畫：二叉樹系列 第七講（完全二叉樹的節點個數）
- 2020 年 3 月 30 日
- 筆記
在上一篇中，我們學習了解了平衡二叉樹，並且利用DFS進行了驗證。在本節中，我們將繼續學習完全二叉樹的相關內容。首先了解一下什麼是完全二叉樹。
01
完全二叉樹
完全二叉樹由滿二叉樹引出，先來了解一下什麼是滿二叉樹：
如果二叉樹中除了葉子結點，每個結點的度都為 2，則此二叉樹稱為滿二叉樹。（二叉樹的度代表某個結點的孩子或者說直接後繼的個數。對於二叉樹而言，1度是只有一個孩子或者說單子樹,2度是有兩個孩子或者說左右子樹都有。）
比如下面這顆：
那什麼又是完全二叉樹呢：
如果二叉樹中除去最後一層節點為滿二叉樹，且最後一層的結點依次從左到右分布，則此二叉樹被稱為完全二叉樹。
比如下面這顆：
而這顆就不是：
熟悉了概念，我們來看題目：
02
第222題：完全二叉樹的節點個數
第222題：給出一個完全二叉樹，求出該樹的節點個數。
說明：
完全二叉樹的定義如下：在完全二叉樹中，除了最底層節點可能沒填滿外，其餘每層節點數都達到最大值，並且最下面一層的節點都集中在該層最左邊的若干位置。若最底層為第 h 層，則該層包含 1~ 2h 個節點。
示例:
輸入:
1
/
2 3
/ /
4 5 6
輸出: 6
03
遞歸求解
首先分析題目，我們很容易可以想到通過遞歸，來求解節點個數。
func countNodes(root *TreeNode) int { if root != nil { return 0 } return 1 + countNodes(root.Right) + countNodes(root.Left) }
但是很明顯，出題者肯定不是要這種答案。因為這種答案和完全二叉樹一毛錢關係都沒有。所以我們繼續思考。
04
經典解法
由於題中已經告訴我們這是一顆完全二叉樹，我們又已知了完全二叉樹除了最後一層，其他層都是滿的，並且最後一層的節點全部靠向了左邊。那我們可以想到，可以將該完全二叉樹可以分割成若干滿二叉樹和完全二叉樹，滿二叉樹直接根據層高h計算出節點為2^h-1，然後繼續計運算元樹中完全二叉樹節點。那如何分割成若干滿二叉樹和完全二叉樹呢？對任意一個子樹，遍歷其左子樹層高left，右子樹層高right，相等左子樹則是滿二叉樹，否則右子樹是滿二叉樹。這裡可能不容易理解，我們看圖。
假如我們有樹如下：
我們看到根節點的左右子樹高度都為3，那麼說明左子樹是一顆滿二叉樹。因為節點已經填充到右子樹了，左子樹必定已經填滿了。所以左子樹的節點總數我們可以直接得到，是2^left – 1，加上當前這個root節點，則正好是2^3，即 8。然後只需要再對右子樹進行遞歸統計即可。
那假如我們的樹是這樣：
我們看到左子樹高度為3，右子樹高度為2。說明此時最後一層不滿，但倒數第二層已經滿了，可以直接得到右子樹的節點個數。同理，右子樹節點+root節點，總數為2^right，即2^2。再對左子樹進行遞歸查找。
根據分析，得出程式碼：
//java class Solution { public int countNodes(TreeNode root) { if (root == null) { return 0; } int left = countLevel(root.left); int right = countLevel(root.right); if (left == right) { return countNodes(root.right) + (1 << left); } else { return countNodes(root.left) + (1 << right); } } private int countLevel(TreeNode root) { int level = 0; while (root != null) { level++; root = root.left; } return level; } }
學會請留言打卡！
讓我看到你的努力~
註：本系列所有教程中都不會用到複雜的語言特性，大家不需要擔心沒有學過語法知識。演算法思想最重要，使用各語言純屬本人愛好。同時，本系列所有程式碼均在leetcode上進行過測試運行，保證其嚴謹性！
