987: 输出用先序遍历创建的二叉树是否为完全二叉树的判定结果
时间: 2023-04-26 19:03:55 浏览: 90
完全二叉树的定义是:除了最后一层外,每一层都必须填满,最后一层可以不填满,但是节点必须从左到右依次填入。因此,判断一个二叉树是否为完全二叉树,需要满足以下条件:
1. 如果一个节点只有右子树,那么这棵树一定不是完全二叉树。
2. 如果一个节点只有左子树或者没有子树,那么这个节点之后的所有节点都必须是叶子节点。
3. 如果一个节点既有左子树又有右子树,那么这个节点之后的所有节点都必须是叶子节点。
因此,我们可以通过先序遍历创建二叉树,并按照上述条件进行判断,来确定这棵二叉树是否为完全二叉树。
相关问题
判定给定二叉树是否为完全二叉树的代码
以下是判断二叉树是否为完全二叉树的 Python 代码:
```python
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def is_complete_tree(root: TreeNode) -> bool:
if not root:
return True
queue = [root]
flag = False
while queue:
node = queue.pop(0)
if node.left:
if flag:
return False
queue.append(node.left)
else:
flag = True
if node.right:
if flag:
return False
queue.append(node.right)
else:
flag = True
return True
```
该算法使用 BFS(广度优先搜索)遍历二叉树,当遍历到第一个没有左子树或右子树的节点时,将 flag 标记为 True,表示后面的节点都应该没有子树。如果后面的节点还有子树,则说明该二叉树不是完全二叉树。
判定给定二叉树是否为完全二叉树的c语言代码
以下是判断二叉树是否为完全二叉树的 C 语言代码:
```c
#include <stdbool.h>
#include <stdlib.h>
struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
};
bool isCompleteTree(struct TreeNode* root) {
if (!root) {
return true;
}
struct TreeNode** queue = (struct TreeNode**)malloc(sizeof(struct TreeNode*) * 1000);
int front = 0, rear = 0;
bool flag = false;
queue[rear++] = root;
while (front < rear) {
struct TreeNode* node = queue[front++];
if (node->left) {
if (flag) {
return false;
}
queue[rear++] = node->left;
} else {
flag = true;
}
if (node->right) {
if (flag) {
return false;
}
queue[rear++] = node->right;
} else {
flag = true;
}
}
free(queue);
return true;
}
```
该算法与 Python 代码类似,使用 BFS 遍历二叉树,当遍历到第一个没有左子树或右子树的节点时,将 flag 标记为 true,表示后面的节点都应该没有子树。如果后面的节点还有子树,则说明该二叉树不是完全二叉树。需要注意的是,C语言中需要手动分配和释放内存。