精選力扣500題 第71題 LeetCode 958. 二叉樹的完全性檢驗【c++/java詳細題解】

1、題目

給定一個二叉樹，確定它是否是一個完全二叉樹，

百度百科中對完全二叉樹的定義如下：

若設二叉樹的深度為 h，除第 h 層外，其它各層 (1～h-1) 的結點數都達到最大個數，第 h 層所有的結點都連續集中在最左邊，這就是完全二叉樹，（注：第 h 層可能包含 1~ 2 h 2^h 2h 個節點，）

示例 1：

輸入：[1,2,3,4,5,6]
輸出：true
解釋：最后一層前的每一層都是滿的（即，結點值為 {1} 和 {2,3} 的兩層），且最后一層中的所有結點（{4,5,6}）都盡可能地向左，

示例 2：

輸入：[1,2,3,4,5,null,7]
輸出：false
解釋：值為 7 的結點沒有盡可能靠向左側，

提示：

1. 樹中將會有 1 到 100個結點，

2、思路

(bfs) O ( n ) O(n) O(n)

完全二叉樹的堆式存貯，堆就是一個完全二叉樹，而完全二叉樹可以用陣串列示，我們將一個值為1~n的連續陣串列示成一個完全二叉樹如下圖所示：

在完全二叉樹中，用 1 表示根節點編號，則對于任意一個節點 x，它的左孩子為 2*x，右孩子為 2*x + 1 ，那么我們可以發現，一顆二叉樹是完全二叉樹當且僅當節點編號依次為 1, 2, 3, ...n 且沒有間隙，換句話說，可以將其表示為一個值為1~n的連續陣列，而在一個值從1開始的連續陣列中，陣列中最大元素值等于陣列大小， 在根節點編號值為1的完全二叉樹則是，節點編號最大值等于節點個數，

因此，我們可以對一顆二叉樹進行廣度優先搜索，這樣搜索出的節點編號序列值恰好可以組成一個升序的陣列，如果編號序列是一個從1開始的無間隔的連續陣列，則該二叉樹為完全二叉樹，

遞回函式設計：

bool dfs(TreeNode* root , int k) //k是當前節點編號

root是當前遍歷的節點，k是當前節點編號，

搜索程序如下：

• 1、我們從根節點開始搜索，并將根節點編號值設定為1，
• 2、然后搜索左子樹，并傳遞其根節點值為2*k，搜索右子樹，并傳遞其根節點值為2*k+1
• 3、在遞回搜索程序中，記錄節點個數n和當前最大節點編號值p，
• 4、最后判斷最大節點值p和節點數n是否相等，相等則該二叉樹是完全二叉樹，否則不是，

遞回邊界：

• 1、題目規定樹中最多有100個節點，如果節點編號k > 100，說明該二叉樹不合法，回傳false，
• 2、遞回到葉子節點，子樹遞回結束，回傳true，

時間復雜度分析： O ( n ) O(n) O(n)，其中 n n n是樹節點個數 ，

3、c++代碼

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    int n = 0, p = 0;  //n是節點數，p是最大節點編號值
    bool isCompleteTree(TreeNode* root) {
        if(!dfs(root,1)) return false; //還沒有遞回到終點就回傳false，說明其不是完全二叉樹
        return n == p;  //判斷最大節點值是否和節點數相等
    }
    bool dfs(TreeNode* root , int k) //k是當前節點編號
    {
        if(!root) return true;  //遞回到了葉子節點
        if(k > 100) return false;
        n++, p = max(p,k); //記錄節點數和最大節點編號值
        return dfs(root->left,2*k)&&dfs(root->right,2*k + 1); //遞回左右子樹
    }
}; 

4、java代碼

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    int n = 0, p = 0; 
    public boolean isCompleteTree(TreeNode root) {
        if(!dfs(root,1)) return false;
        return n == p;
    }
    public boolean dfs(TreeNode root , int k) //k是當前節點編號
    {
        if(root == null) return true;  //遞回到了葉子節點
        if(k > 100) return false;
        n++;  p = Math.max(p,k); //記錄節點數和最大節點編號值
        return dfs(root.left,2*k)&&dfs(root.right,2*k + 1); //遞回左右子樹
    }
}

原題鏈接： 958. 二叉樹的完全性檢驗