题解 | #判断是不是完全二叉树#
判断是不是完全二叉树
https://www.nowcoder.com/practice/8daa4dff9e36409abba2adbe413d6fae
1 解题思路
本题判断是否是完全二叉树,根据完全二叉树的性质,考虑使用按层次遍历检查。可以先枚举所有不是完全二叉树的形态,当程序检查到该形态后可以直接返回false,全部遍历完成后证明所有结点符合要求,返回true。
所有不是完全二叉树的形态:
(1)某一个结点有右孩子,没有左孩子;
(2)某一个结点只有左结点,右侧的兄弟结点或堂兄弟结点不存在;
(3)某一个结点只有左结点或一个结点都没有,右侧兄弟结点或堂兄弟结点有孩子结点。
/** * struct TreeNode { * int val; * struct TreeNode *left; * struct TreeNode *right; * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * }; */ class Solution { public: /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param root TreeNode类 * @return bool布尔型 */ bool isCompleteTree(TreeNode* root) { if(!root) return true; vector<TreeNode*> queue; //按层次遍历,队列里存放同一层所有结点。这里除了vector也能用dequeue。 queue.push_back(root); bool mark = false; //哨兵,如果某个结点只有左结点或一个结点也没有,设为true。注意mark不能再while循环中定义,否则会漏掉不是完全二叉树的第二种形态的情况,可以验证自行验证。 while(!queue.empty()){ for(TreeNode* tmp:queue){ if(mark && (tmp->left||tmp->right)) //不是完全二叉树的第二种形态或第三种形态,直接返回。 return false; if(!tmp->left && tmp->right)//不是完全二叉树的第一种形态。 return false; if(!tmp->left || !tmp->right) //首次遇到不完全结点时,mark设置为true mark=true; } int count = queue.size(); //当前层所有结点遍历结束,依次出队,将下一层结点按顺序进入队列。 while(count>0){ TreeNode* front = queue.at(0); queue.erase(queue.begin()); if(front->left) queue.push_back(front->left); if(front->right) queue.push_back(front->right); count--; } } //队列为空说明所有结点遍历完成,正常退出循环说明都符合完全二叉树要求,返回true。 return true; } };