LeetCode958 二叉树的完全性检验

给定一个二叉树，确定它是否是一个完全二叉树。

百度百科中对完全二叉树的定义如下：

若设二叉树的深度为 h，除第 h 层外，其它各层 (1～h-1) 的结点数都达到最大个数，第 h 层所有的结点都连续集中在最左边，这就是完全二叉树。（注：第 h 层可能包含 1~ 2h 个节点。）

自己用的是本方法，先计算一个深度（一直往左走），可能不是真正的深度但是没关系。对于depth-2的深度的节点直接按层次遍历压入队列，然后每一层开始的时候检验上一层数目是否正确；对于depth-1层就照样压入，遇到第一个nullptr的时候就跳出，检查后面所有的子节点是否都为nullptr；对于depth的节点直接检查是否全为叶子。

 1 /**
 2  * Definition for a binary tree node.
 3  * struct TreeNode {
 4  *     int val;
 5  *     TreeNode *left;
 6  *     TreeNode *right;
 7  *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 8  * };
 9  */
10 class Solution {
11 
12 public:
13     bool isCompleteTree(TreeNode* root) {
14         if(root==nullptr)
15             return true;
16         int depth=get_depth(root);
17         queue<TreeNode*> qTree;
18         qTree.push(root);
19         int flag=0, aimlen=1;
20         for(int i=2;i<=depth;++i){
21             if(i<depth-1){
22                 int curlen=qTree.size();
23                 if(curlen!=aimlen )
24                     return false;
25                 for(int j=0;j<curlen;++j){
26                     TreeNode* temp=qTree.front();
27                     qTree.pop();
28                     if(temp->left!=nullptr)
29                         qTree.push(temp->left);
30                     if(temp->right!=nullptr)
31                         qTree.push(temp->right);
32                 }
33                 aimlen*=2;
34             }
35             else if(i==depth-1){
36                 int curlen=qTree.size();
37                 if(curlen!=aimlen )
38                     return false;
39                 int j=0;
40                 for(;j<curlen;++j){
41                     TreeNode* temp=qTree.front();
42                     qTree.pop();
43                     if(temp->left==nullptr){
44                         if(temp->right!=nullptr)
45                             return false;
46                         break;
47                     }
48                     else if(temp->right==nullptr){
49                         qTree.push(temp->left);
50                         break;
51                     }
52                     else{
53                         qTree.push(temp->left);
54                         qTree.push(temp->right);
55                     }
56                 }
57                 for(j=j+1;j<curlen;++j){
58                     TreeNode* temp=qTree.front();
59                     qTree.pop();
60                     if(temp->left!=nullptr || temp->right!=nullptr)
61                         return false;
62                 }
63             }
64             else{
65                 while(!qTree.empty()){
66                     TreeNode* temp=qTree.front();
67                     qTree.pop();
68                     if(temp->left!=nullptr || temp->right!=nullptr)
69                         return false;
70                 }
71             }
72         }
73         return true;
74     }
75 
76     int get_depth(TreeNode* root){
77         int depth=1;
78         while(root!=nullptr){
79             root=root->left;
80             ++depth;
81         }
82         return depth;
83     }
84 };

看过答案后发现可以直接用编号检查，因为完全二叉树按照层次遍历刚好是连续的n个数。对于编号为i的节点，他的两个子节点编号分别为2*i,2*i+1；所以只要寻找是否有节点的编号超出了节点个数

 1 /**
 2  * Definition for a binary tree node.
 3  * struct TreeNode {
 4  *     int val;
 5  *     TreeNode *left;
 6  *     TreeNode *right;
 7  *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 8  * };
 9  */
10 class Solution {
11 public:
12     bool isCompleteTree(TreeNode* root) {
13         size_ = count(root);
14         bool bOK = true;
15         sovle(root,0, bOK );
16         return bOK;
17     }
18 
19     int count(TreeNode* curr)
20     {
21         if(curr==NULL) return 0;
22         int ans=1;
23         ans+= count(curr->left);
24         ans+= count(curr->right);
25         return ans;
26     }
27 
28     void sovle(TreeNode* curr, int i, bool& bOK)
29     {
30         if(curr==NULL) return;
31 
32         if(curr->left!=NULL)
33         {
34             int left = 2*i+1;
35             if(left>=size_) 
36             {
37                 bOK = false;
38                 return;
39             }
40             sovle(curr->left, left, bOK);
41             if(!bOK) return;
42         }
43         if(curr->right!=NULL)
44         {
45             int right = 2*i+2;
46             if(right>=size_)
47             {
48                 bOK = false;
49                 return;
50             }
51             sovle(curr->right, right, bOK);
52             if(!bOK) return;
53         }
54         
55     }
56 private:
57     int size_;
58 };
59 
60 作者：brucechen135
61 链接：https://leetcode-cn.com/problems/check-completeness-of-a-binary-tree/solution/er-cha-dui-de-jie-gou-xing-by-brucechen135/
62 来源：力扣（LeetCode）
63 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。