Complete Binary Tree

Complete Binary Tree.png

解題思路 ：

從 root 開始把所有節點用 BFS 方式放入 vector ( 節點只要不是 nullptr 就放入左跟右 child 如果 child 是 nullptr 也照樣放入 ) 存完整個 tree 之後 接著從 vector 後面檢查 只要是 nullptr 就忽略 直到找到第一個非 nullptr 的值 以此 index 為起點往前找 如果還能找到任何一個 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;
}

};