如何判断一个二叉树是否是合法二叉树？

一个合法的二叉树需要满足以下几个条件：
1. 每个节点最多有两个子节点。
2. 左子树和右子树都必须是合法的二叉树。
3. 左子树中所有节点的值都小于当前节点的值，右子树中所有节点的值都大于当前节点的值。

因此，判断一个二叉树是否合法可以通过递归实现。从根节点开始，递归判断左子树和右子树是否合法，同时判断当前节点的值是否大于左子树中所有节点的值，是否小于右子树中所有节点的值。如果满足以上条件，则这是一个合法的二叉树。

相关问题

判断一个二叉树是否是合法二叉树，并写出Python代码

判断一棵二叉树是否合法需要满足以下条件：

1. 左右子树都必须是合法的二叉树
2. 左子树的最大值小于当前节点的值
3. 右子树的最小值大于当前节点的值

以下是Python代码实现：

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def isValidBST(root: TreeNode) -> bool:
    def helper(node, lower=float('-inf'), upper=float('inf')):
        if not node:
            return True
        if node.val <= lower or node.val >= upper:
            return False
        if not helper(node.right, node.val, upper):
            return False
        if not helper(node.left, lower, node.val):
            return False
        return True
    return helper(root)

判断一个树是否是完全二叉树

判断一个树是否是完全二叉树，可以通过深度优先搜索（DFS）或广度优先搜索（BFS）的方法来检查每个节点是否有两个子节点，且最后一个非空层的节点都尽可能地集中在左边。

以下是一个使用递归方法检查完全二叉树的C语言代码示例：

#include <stdio.h>
#include <stdbool.h>

// 定义二叉树结点结构
typedef struct TreeNode {
    int val;
    struct TreeNode *left, *right;
} TreeNode;

// 判断是否存在合法的右子节点
bool hasValidRightChild(TreeNode* node) {
    return (node->right != NULL);
}

// 检查给定节点及其父节点是否构成完全二叉树
bool isValidCompleteBinaryTreeHelper(TreeNode* root, int level) {
    if (root == NULL) return true; // 根节点为空时返回true

    if (!hasValidRightChild(root)) { // 如果当前节点没有右孩子，则直接检查左孩子的存在及下一层
        return isValidCompleteBinaryTreeHelper(root->left, level + 1);
    } else if (level % 2 == 0) { // 如果层数为偶数（根节点的层次），则要求当前节点有左子树且右子树为空
        return (root->left != NULL && !hasValidRightChild(root->right));
    } else { // 层数为奇数（非根节点），要求左右子树均存在
        return (root->left != NULL && root->right != NULL);
    }
}

// 主函数：从根节点开始检查整棵树
bool isCompleteBinaryTree(TreeNode* root) {
    return isValidCompleteBinaryTreeHelper(root, 0);
}

int main() {
    // 测试用例
    TreeNode* tree = // 填充你的二叉树实例
    ...
    if (isCompleteBinaryTree(tree)) {
        printf("The tree is a complete binary tree.\n");
    } else {
        printf("The tree is not a complete binary tree.\n");
    }
    return 0;
}

在这个代码中，`isValidCompleteBinaryTreeHelper` 函数用于递归遍历树并检查条件。如果所有层都有两个节点，除了可能的最后一层，那么这棵树就是完全二叉树。