数据结构：二叉树精选 9 道 OJ 练习

104. 二叉树的最大深度

题目介绍

方法一

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */

// 问题的本质：二叉树的最大深度=fmax(左子树的深度，右子树的深度)
int maxDepth(struct TreeNode* root) {
    // 处理：空树的情况
    if (root == NULL)
        return 0;
    return fmax(maxDepth(root->left), maxDepth(root->right)) + 1;
}

965. 单值二叉树

题目介绍

方法一

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
bool isUnivalTree(struct TreeNode* root) {
    // 处理：空树的情况
    if (root == NULL)
        return true;
    
    // 使用 if 判断：如果双亲节点的值不等于孩子节点的值
    if (root->left && root->left->val != root->val)
        return false;
    if (root->right && root->right->val != root->val)
        return false;
    
    // 在左子树中进行递归
    bool ret = isUnivalTree(root->left);
    if (!ret)
        return false;
    
    // 在右子树中进行递归
    ret = isUnivalTree(root->right);
    if (!ret)
        return false;
    
    // 返回通过所有检测的返回值
    return true;
}

100. 相同的树

题目介绍

方法一

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
bool isSameTree(struct TreeNode* p, struct TreeNode* q) {
    // 处理：两颗树都为空树的情况
    if (p == NULL && q == NULL)
        return true;
    
    // 处理：其中一颗树为空树的情况
    if (p == NULL || q == NULL)
        return false;
    
    // 使用 if 判断：如果的两棵树的节点的值不相等
    if (p->val != q->val)
        return false;
    
    // 递归判断左子树和右子树的所有节点是否相等
    bool ret = isSameTree(p->left, q->left);
    if (!ret)
        return false;
    
    // 这里是当我们未遍历完所有的节点时就已经出现了节点不匹配的情况的话，我们就先让递归提前结束
    ret = isSameTree(p->right, q->right);
    if (!ret)
        return false;
    
    return true;
}

101. 对称二叉树

题目介绍

方法一

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
bool _isSymmetric(struct TreeNode* root1, struct TreeNode* root2) {
    // 处理：左子树和右子树都为空树的情况
    if (root1 == NULL && root2 == NULL)
        return true;
    
    // 处理：左子树和右子树中有一颗树是空树
    if (root1 == NULL || root2 == NULL)
        return false;
    
    // 处理：左子树和右子树都不为空树，但是对应位置的节点的值却不相等
    if (root1->val != root2->val)
        return false;
    
    // 进行递归遍历左子树和右子树中的节点
    // 比较：'左子树的左孩子 and 右子树的右孩子'
    bool ret = _isSymmetric(root1->left, root2->right);
    if (!ret)
        return false;
    
    // 比较：'左子树的右孩子 and 右子树的左孩子'
    ret = _isSymmetric(root1->right, root2->left);
    if (!ret)
        return false;
    
    return true;
}

bool isSymmetric(struct TreeNode* root) {
    // 确保进行判断的这颗树是一颗合法的树
    if (!root)
        return false;
    
    // 调用子函数解决问题
    return _isSymmetric(root->left, root->right);
}

572. 另一棵树的子树

题目介绍

方法一

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
bool isSameTree(struct TreeNode* root1, struct TreeNode* root2) {
    // 处理：'空树 + 遍历到空节点' 的情况
    if (root1 == NULL && root2 == NULL)
        return true;
    
    // 处理：其中一棵树为空树另一棵树不为空树的情况
    if (root1 == NULL || root2 == NULL)
        return false;
    
    // 处理：两棵树都不为空树但是，但是当前遍历到的节点的值不相等
    if (root1->val != root2->val)
        return false;
    
    // 进行递归判断两棵树的其他节点
    bool ret = isSameTree(root1->left, root2->left);
    if (!ret)
        return false;
    ret = isSameTree(root1->right, root2->right);
    if (!ret)
        return false;
    
    return true;
}

bool isSubtree(struct TreeNode* root, struct TreeNode* subRoot) {
    // 思路：判断一棵树是不是另一棵树的子树
    // （1）二叉树的寻找某个节点操作 + （2）判断两棵二叉树是否相等
    
    // 处理：'空树 + 遍历到空节点' 的情况
    if (root == NULL)
        return false;
    
    // 使用 if 判断：如果我们找到这个节点
    if (isSameTree(root, subRoot))
        return true;
    
    // 进行递归遍历
    // 递归左子树进行寻找
    bool ret = isSubtree(root->left, subRoot);
    if (ret)
        return ret;
    
    // 递归右子树进行寻找
    ret = isSubtree(root->right, subRoot);
    if (ret)
        return ret;
    
    return false;
}

KY11 二叉树遍历

题目介绍

开始挑战：KY11 二叉树遍历

方法一

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

// 二叉树的存储结构
typedef struct BinaryTreeNode {
    int data;
    struct BinaryTreeNode* left;
    struct BinaryTreeNode* right;
} BTNode;

// 实现：'二叉树的中序遍历'操作
void InOrder(BTNode* root) {
    // 处理：'空树 + 空节点'的情况
    if (root == NULL)
        return;
    
    // 递归进行中序遍历
    InOrder(root->left);
    printf("%c ", root->data);
    InOrder(root->right);
}

// 实现：'根据前序遍历字符串创建出一棵二叉树'
BTNode* BTCreate(char* arr, int* pi) {
    // 先处理空节点
    if (arr[*pi] == '#') {
        (*pi)++;
        return NULL;
    }
    
    // 再处理非空节点
    // 使用 malloc 为树节点开辟空间
    BTNode* root = (BTNode*)malloc(sizeof(BTNode));
    
    // 为节点进行赋值
    root->data = arr[*pi];
    (*pi)++;
    
    // 为节点创建结构
    root->left = BTCreate(arr, pi);
    root->right = BTCreate(arr, pi);
    
    // 返回创建出的二叉树的根节点
    return root;
}

int main() {
    // 获取数据
    char arr[100];
    scanf("%s", arr);
    int i = 0;
    
    // 处理数据
    BTNode* root = BTCreate(arr, &i);
    
    // 输出数据
    InOrder(root);
    
    return 0;
}

226. 翻转二叉树

题目介绍

方法一

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */

// 实现两个变量的值的交换
// 注意：这里要写 struct 不要忘记了，因为这里的 struct TreeNode 才是 a 的类型啊！！！
void Swap(struct TreeNode** a, struct TreeNode** b) {
    // 注意：Swap 函数处理的是树的节点，需要进行判空操作
    if (a == NULL && b == NULL)
        return;
    
    struct TreeNode* tmp = *a;
    *a = *b;
    *b = tmp;
}

struct TreeNode* invertTree(struct TreeNode* root) {
    // 处理空树的情况（同时也是递归结束的条件 ---> 传入参数的空节点的时候，停止递归）
    if (root == NULL)
        return NULL;
    
    // 交换遍历到的节点的左右孩子
    Swap(&root->left, &root->right);
    
    // 递归处理其他的节点
    invertTree(root->left);
    invertTree(root->right);
    
    // 将处理后的二叉树的根节点返回
    return root;
}

110. 平衡二叉树

题目介绍

方法一

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */

//--------------实现求一个求树高度的方法--------------
int BTHeight(struct TreeNode* root) {
    // 处理空树的情况（同时也是递归结束的条件 ---> 传入参数的空节点的时候，停止递归）
    if (root == NULL)
        return 0;
    
    // 递归处理左子树的情况
    int leftHeight = BTHeight(root->left);
    
    // 递归处理右子树的情况
    int rightHeight = BTHeight(root->right);
    
    return (leftHeight > rightHeight ? leftHeight : rightHeight) + 1;
}

bool isBalanced(struct TreeNode* root) {
    // 思路：
    // 1. 遍历的这棵树中的所以节点
    // 2. 对遍历到的每个节点的左右子树的根节点调用 BTHeight 函数
    // 3. 计算所返回的两个值的差值
    
    // 处理空树的情况（同时也是递归结束的条件 ---> 传入参数的空节点的时候，停止递归）
    if (root == NULL)
        return true;
    
    /*-------------第一步：求出分别以当前遍历到的节点的左右子树为根节点的树的高度-------------*/
    int leftTree = BTHeight(root->left);
    int rightTree = BTHeight(root->right);
    
    /*-------------第二步：计算左右子树的高度差-------------*/
    if (abs(leftTree - rightTree) > 1) {
        return false;
    }
    
    /*-------------第三步：递归遍历这棵二叉树中的所有的节点-------------*/
    return isBalanced(root->left) && isBalanced(root->right);
}