二叉树合理性判断代码
时间: 2024-05-23 12:07:38 浏览: 105
二叉树合理性判断的代码可以通过遍历二叉树来实现。具体而言,可以使用深度优先遍历或广度优先遍历的方式来判断二叉树是否合理。以下是一种深度优先遍历的方式:
```
bool isValidBST(TreeNode* root) {
return isValidBST(root, LONG_MIN, LONG_MAX);
}
bool isValidBST(TreeNode* root, long minVal, long maxVal) {
if (!root) return true;
if (root->val <= minVal || root->val >= maxVal) return false;
return isValidBST(root->left, minVal, root->val) && isValidBST(root->right, root->val, maxVal);
}
```
该代码使用递归的方式遍历二叉树,同时记录当前节点可取的最大值和最小值。当节点的值超出这个范围时,就可以判断该二叉树不合理。
相关问题
完全二叉树的判断代码
以下是判断完全二叉树的代码实现:
```cpp
bool isCompleteTree(TreeNode* root) {
queue<TreeNode*> q;
q.push(root);
bool end = false;
while (!q.empty()) {
TreeNode* node = q.front();
q.pop();
if (node == nullptr) {
end = true;
} else {
if (end) {
return false;
}
q.push(node->left);
q.push(node->right);
}
}
return true;
}
```
该算法使用了层序遍历的思想,将每一层的节点按顺序加入队列中,如果在遍历过程中出现了空节点,那么后面的节点必须全部为空节点才能保证是完全二叉树,否则就不是完全二叉树。
完全二叉树判断的伪代码
完全二叉树判断的伪代码如下:
1. 定义一个队列,用于存储待检查的节点。
2. 将根节点入队。
3. 循环执行以下步骤,直到队列为空:
1. 出队一个节点,并检查其左右子节点是否存在。
- 如果左子节点不存在但右子节点存在,返回 false。
- 如果左子节点存在但右子节点不存在,或者上一层已经出现了左右子节点不全的情况,后续的节点必须都是叶子节点,否则返回 false。
2. 如果左子节点存在,则将其入队。
3. 如果右子节点存在,则将其入队。
4. 如果队列为空,且所有节点都满足上述条件,则返回 true,表示是完全二叉树;否则返回 false。
伪代码实现:
```
function isCompleteBinaryTree(root):
queue = new Queue()
queue.enqueue(root)
leafNodeFound = false
while queue is not empty:
node = queue.dequeue()
if node.left is not null:
if leafNodeFound or node.right is null:
return false
queue.enqueue(node.left)
if node.right is not null:
if leafNodeFound:
return false
queue.enqueue(node.right)
else:
leafNodeFound = true
return true
```
注意:上述伪代码假设已经定义了一个队列数据结构,并实现了相应的 enqueue 和 dequeue 操作。