Complete Binary Tree.png
解題思路 ：
從 root 開始把所有節(jié)點(diǎn)用 BFS 方式放入 vector ( 節(jié)點(diǎn)只要不是 nullptr 就放入左跟右 child 如果 child 是 nullptr 也照樣放入 ) 存完整個 tree 之後 接著從 vector 後面檢查 只要是 nullptr 就忽略 直到找到第一個非 nullptr 的值 以此 index 為起點(diǎn)往前找 如果還能找到任何一個 nullptr 則 return false 代表不是 complete binary tree ( CBT 的特性 nullptr 一定只能在尾端 )
C++ code :
<pre><code>
/**
- Definition of TreeNode:
- class TreeNode {
- public:
int val;TreeNode *left, *right;TreeNode(int val) {this->val = val;this->left = this->right = NULL;}- }
*/
class Solution {
public:
/**
* @param root, the root of binary tree.
* @return true if it is a complete binary tree, or false.
/
bool isComplete(TreeNode root) {
// Write your code here
vector<TreeNode*> Q;
Q.push_back(root);
for(int i = 0; i < Q.size(); i++)
{
TreeNode *tmp = Q[i];
if(tmp)
{
Q.push_back(tmp->left);
Q.push_back(tmp->right);
}
}
int index = 0;
for(int i = Q.size() - 1; i >= 0; i--)
{
if(Q[i]){
index = i;
break;
}
}
for(int i = index - 1; i >= 0; i--)
{
if(!Q[i]) return false;
}
return true;
}
};
