1 简介
完全二叉树特点:
(1)叶子结点都在最底下的两层;
(2)最后一层的叶子结点都靠左排列,即中间没有空洞;
(3)除最后一层外,其他层的节点个数都要达到最大;
2 相关题目
2.1 完全二叉树插入器
这里实际上就是进行了层序遍历,代码具体如下:
class CBTInserter {
private:
TreeNode* r;
public:
CBTInserter(TreeNode* root) {
r = root;
}
int insert(int v) {
if (!r)
{
r = new TreeNode(v);
return v;
}
else
{
TreeNode* tmp;;
queue<TreeNode*> q;
q.push(r);
while (!q.empty())
{
tmp = q.front();
q.pop();
if (!tmp->left)
{
tmp->left = new TreeNode(v);
break;
}
else if (!tmp->right)
{
tmp->right = new TreeNode(v);
break;
}
q.push(tmp->left);
q.push(tmp->right);
}
return tmp->val;
}
}
TreeNode* get_root() {
return r;
}
};
2.2
2.3
2.4
3