【基础数据结构】二叉树的基本性质

例题1

单值二叉树

如果二叉树每个节点都具有相同的值，那么该二叉树就是单值二叉树。

只有给定的树是单值二叉树时，才返回?true；否则返回?false。

示例 1：

输入：[1,1,1,1,1,null,1]
输出：true

示例 2：

输入：[2,2,2,5,2]
输出：false

提示：

1. 给定树的节点数范围是?[1, 100]。
2. 每个节点的值都是整数，范围为?[0, 99]?。

编译环境Dev-cpp(C++)

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

typedef struct TreeNode {
    int val;  // 节点值
    struct TreeNode* left;  // 左子树指针
    struct TreeNode* right;  // 右子树指针
} TreeNode;

// 判断二叉树是否为单值二叉树的函数
bool isUnivalTree(struct TreeNode* root) {
    if (root == NULL) {
        return true;  // 空树是单值二叉树
    }

    // 检查左子树的值和根节点的值是否相等
    if (root->left != NULL && root->left->val != root->val) {
        return false;
    }

    // 检查右子树的值和根节点的值是否相等
    if (root->right != NULL && root->right->val != root->val) {
        return false;
    }

    // 递归判断左右子树是否为单值二叉树
    return isUnivalTree(root->left) && isUnivalTree(root->right);
}

// 创建二叉树节点的函数
struct TreeNode* createNode(int val) {
    struct TreeNode* newNode = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    newNode->val = val;
    newNode->left = NULL;
    newNode->right = NULL;
    return newNode;
}

// 构建二叉树的函数
struct TreeNode* buildTree() {
    struct TreeNode* root = createNode(1);
    root->left = createNode(1);
    root->right = createNode(1);
    root->left->left = createNode(1);
    root->left->right = createNode(1);
    root->right->right = createNode(1);
    return root;
}

// 释放二叉树节点内存的函数
void freeTree(struct TreeNode* root) {
    if (root == NULL) {
        return;
    }
    freeTree(root->left);
    freeTree(root->right);
    free(root);
}

int main() {
    // 构建二叉树
    struct TreeNode* root = buildTree();

    // 判断二叉树是否为单值二叉树
    bool result = isUnivalTree(root);

    // 打印结果
    if (result) {
        printf("The binary tree is a unival tree.\n");
    } else {
        printf("The binary tree is not a unival tree.\n");
    }

    // 释放二叉树节点内存
    freeTree(root);

    return 0;
}

例题2

相同的树

给你两棵二叉树的根节点?p?和?q?，编写一个函数来检验这两棵树是否相同。

如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。

示例 1：

输入：p = [1,2,3], q = [1,2,3]
输出：true

示例 2：

输入：p = [1,2], q = [1,null,2]
输出：false

示例 3：

输入：p = [1,2,1], q = [1,1,2]
输出：false

提示：

• 两棵树上的节点数目都在范围?[0, 100]?内
• ?<= Node.val <=?

编译环境Dev-cpp(C++)

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

typedef struct TreeNode {
    int val;  // 节点值
    struct TreeNode* left;  // 左子树指针
    struct TreeNode* right;  // 右子树指针
} TreeNode;

// 判断两棵二叉树是否相同的函数
bool isSameTree(struct TreeNode* p, struct TreeNode* q) {
    if (p == NULL && q == NULL) {
        return true;  // 两棵树均为空，认为它们相同
    }

    if (p == NULL || q == NULL) {
        return false;  // 一棵树为空，另一棵不为空，认为它们不相同
    }

    if (p->val != q->val) {
        return false;  // 节点值不相等，认为两棵树不相同
    }

    // 递归判断左右子树是否相同
    return isSameTree(p->left, q->left) && isSameTree(p->right, q->right);
}

// 创建二叉树节点的函数
struct TreeNode* createNode(int val) {
    struct TreeNode* newNode = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    newNode->val = val;
    newNode->left = NULL;
    newNode->right = NULL;
    return newNode;
}

// 构建第一棵二叉树的函数
struct TreeNode* buildTree1() {
    struct TreeNode* root = createNode(1);
    root->left = createNode(2);
    root->right = createNode(3);
    return root;
}

// 构建第二棵二叉树的函数
struct TreeNode* buildTree2() {
    struct TreeNode* root = createNode(1);
    root->left = createNode(2);
    root->right = createNode(3);
    return root;
}

// 释放二叉树节点内存的函数
void freeTree(struct TreeNode* root) {
    if (root == NULL) {
        return;
    }
    freeTree(root->left);
    freeTree(root->right);
    free(root);
}

int main() {
    // 构建第一棵二叉树
    struct TreeNode* p = buildTree1();

    // 构建第二棵二叉树
    struct TreeNode* q = buildTree2();

    // 检查两棵二叉树是否相同
    bool result = isSameTree(p, q);

    // 打印结果
    if (result) {
        printf("The two binary trees are the same.\n");
    } else {
        printf("The two binary trees are not the same.\n");
    }

    // 释放二叉树节点内存
    freeTree(p);
    freeTree(q);

    return 0;
}

例题3

对称二叉树

给你一个二叉树的根节点?root?， 检查它是否轴对称。

示例 1：

输入：root = [1,2,2,3,4,4,3]
输出：true

示例 2：

输入：root = [1,2,2,null,3,null,3]
输出：false

提示：

• 树中节点数目在范围?[1, 1000]?内
• -100 <= Node.val <= 100

编译环境Dev-cpp(C++)

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

typedef struct TreeNode {
    int val;  // 节点值
    struct TreeNode* left;  // 左子树指针
    struct TreeNode* right;  // 右子树指针
} TreeNode;

// 判断左右子树是否对称的辅助函数
bool isSymmetricHelper(struct TreeNode* left, struct TreeNode* right) {
    if (left == NULL && right == NULL) {
        return true;  // 左右子树均为空，认为它们对称
    }

    if (left == NULL || right == NULL) {
        return false;  // 左右子树一个为空，一个不为空，认为它们不对称
    }

    if (left->val != right->val) {
        return false;  // 左右子树根节点值不相等，认为它们不对称
    }

    // 递归判断左子树的左子树与右子树的右子树是否对称
    // 以及左子树的右子树与右子树的左子树是否对称
    return isSymmetricHelper(left->left, right->right) && isSymmetricHelper(left->right, right->left);
}

// 判断二叉树是否对称的函数
bool isSymmetric(struct TreeNode* root) {
    if (root == NULL) {
        return true;  // 空树认为是对称的
    }

    // 调用辅助函数判断左右子树是否对称
    return isSymmetricHelper(root->left, root->right);
}

// 创建二叉树节点的函数
struct TreeNode* createNode(int val) {
    struct TreeNode* newNode = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    newNode->val = val;
    newNode->left = NULL;
    newNode->right = NULL;
    return newNode;
}

// 构建二叉树的函数
struct TreeNode* buildTree() {
    struct TreeNode* root = createNode(1);
    root->left = createNode(2);
    root->right = createNode(2);
    root->left->left = createNode(3);
    root->left->right = createNode(4);
    root->right->left = createNode(4);
    root->right->right = createNode(3);
    return root;
}

// 释放二叉树节点内存的函数
void freeTree(struct TreeNode* root) {
    if (root == NULL) {
        return;
    }
    freeTree(root->left);
    freeTree(root->right);
    free(root);
}

int main() {
    // 构建二叉树
    struct TreeNode* root = buildTree();

    // 检查二叉树是否对称
    bool result = isSymmetric(root);

    // 打印结果
    if (result) {
        printf("The binary tree is symmetric.\n");
    } else {
        printf("The binary tree is not symmetric.\n");
    }

    // 释放二叉树节点内存
    freeTree(root);

    return 0;
}

?