• 【LeetCode-二叉树训练】

    在这里插入图片描述每一个不曾起舞的日子，都是对生命的辜负。

    二叉树训练

    1. 单值二叉树🚀

    965. 单值二叉树

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

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

    示例 1：

    img

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

    • 1
    • 2

    示例 2：

    img

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

    • 1
    • 2

    提示：

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

    思路：通过root与其两个子节点判断是否相等，为了通过这个步骤遍历树的所有节点，采用递归方式去遍历即可

    /**
 * 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(root->left && root->val != root->left->val)
    return false;

    if(root->right && root->val != root->right->val)
    return false;

    return isUnivalTree(root->left)&&isUnivalTree(root->right);
      
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23

    在这里插入图片描述

    2. 相同的树🚀

    100. 相同的树

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

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

    示例 1：

    img

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

    • 1
    • 2

    示例 2：

    img

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

    • 1
    • 2

    示例 3：

    img

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

    • 1
    • 2

    提示：

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

    思路：相同的树必须满足按照相同步骤能够同时访问到空节点，并且每次访问的值都相同，因此仍然是遍历树的所有节点，此时只需要递归即可。

    /**
 * 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|| p->val != q->val)
    {
        return false;
    }

    return isSameTree(p->left,q->left) && isSameTree(p->right,q->right);

    
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25

    在这里插入图片描述

    3. 对称二叉树🚀

    101. 对称二叉树

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

    示例 1：

    img

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

    • 1
    • 2

    示例 2：

    img

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

    • 1
    • 2

    提示：

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

    思路：对称与相同具有相似之处，只需要将上面递归的参数变成相对的即可，当然头结点为空也是对称的，为了这种情况，需要吧递归放到子函数中。

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

bool balanceTree(struct TreeNode* left,struct TreeNode* right)
{
    if(left == NULL && right == NULL)
    {
        return true;
    }

    if(left == NULL || right == NULL|| left->val != right->val)
    {
        return false;
    }

    return balanceTree(left->left,right->right) && balanceTree(left->right,right->left);
}
bool isSymmetric(struct TreeNode* root){
    if(root == NULL)
       return true;
       
    return balanceTree(root->left,root->right);
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29

    在这里插入图片描述

    4. 二叉树的前序遍历🚀

    144. 二叉树的前序遍历

    给你二叉树的根节点 root ，返回它节点值的 前序 遍历。

    示例 1：

    img

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

    • 1
    • 2

    示例 2：

    输入：root = []
输出：[]

    • 1
    • 2

    示例 3：

    输入：root = [1]
输出：[1]

    • 1
    • 2

    示例 4：

    img

    输入：root = [1,2]
输出：[1,2]

    • 1
    • 2

    示例 5：

    img

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

    • 1
    • 2

    提示：

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

    思路：通过之前对二叉树的学习我们知道二叉树前序遍历的逻辑，不过前者是直接打印，这道题则是需要返回一个数组，因此，我们需要计算其长度，开辟等大小的数组，并随着不断遍历一直++下标。

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


/**
 * Note: The returned array must be malloced, assume caller calls free().
 */

int TreeSize(struct TreeNode* root)
{
    if(root == NULL)
        return 0;
    
    return TreeSize(root->left) + TreeSize(root->right) + 1;
}

void preorder(struct TreeNode* root,int* arr,int* pi)
{
    if(root == NULL)
        return;
   
     arr[(*pi)] = root->val;
    (*pi)++;
   preorder(root->left,arr,pi);
   preorder(root->right,arr,pi);
    
}
int* preorderTraversal(struct TreeNode* root, int* returnSize){
    
    int n = TreeSize(root);
    int* arr = (int*)malloc(sizeof(int)*n);
    int i = 0;
    preorder(root,arr,&i);
    *returnSize = n;

    return arr;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43

    在这里插入图片描述

    5. 二叉树的中序遍历🚀

    94. 二叉树的中序遍历

    给定一个二叉树的根节点 root ，返回 它的 中序 遍历 。

    示例 1：

    img

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

    • 1
    • 2

    示例 2：

    输入：root = []
输出：[]

    • 1
    • 2

    示例 3：

    输入：root = [1]
输出：[1]

    • 1
    • 2

    提示：

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

    与4题的思路一样，只不过是把前序变成中序

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


/**
 * Note: The returned array must be malloced, assume caller calls free().
 */

int TreeSize(struct TreeNode* root)
{
    if(root == NULL)
    return 0;
    
    return TreeSize(root->left)+TreeSize(root->right) + 1;
}
void inorder(struct TreeNode* root,int* a,int* pi)
{
    if(root == NULL)
    return;
    inorder(root->left,a,pi);
    a[(*pi)] = root->val;
    (*pi)++;
    inorder(root->right,a,pi);
    
    
}
int* inorderTraversal(struct TreeNode* root, int* returnSize){
    int n = TreeSize(root);
    int* arr = (int*)malloc(sizeof(int)*n);
    *returnSize = n;

    int i=0;
    inorder(root,arr,&i);
    return arr;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41

    因此，后序遍历也就知道如何进行展开了，这里就不演示了。自己动手哦

    145. 二叉树的后序遍历

    6. 另一棵树的子树🚀

    572. 另一棵树的子树

    难度简单819收藏分享切换为英文接收动态反馈

    给你两棵二叉树 root 和 subRoot 。检验 root 中是否包含和 subRoot 具有相同结构和节点值的子树。如果存在，返回 true ；否则，返回 false 。

    二叉树 tree 的一棵子树包括 tree 的某个节点和这个节点的所有后代节点。tree 也可以看做它自身的一棵子树。

    示例 1：

    img

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

    • 1
    • 2

    示例 2：

    img

    输入：root = [3,4,5,1,2,null,null,null,null,0], subRoot = [4,1,2]
输出：false

    • 1
    • 2

    提示：

    • root 树上的节点数量范围是 [1, 2000]
    • subRoot 树上的节点数量范围是 [1, 1000]
    • -104 <= root.val <= 104
    • -104 <= subRoot.val <= 104

    思路：判断另一颗树是否是子树，无非就是在原树中遍历节点，直到这个节点为根的树与这个树相等即可，因此这里用到了第二题的函数。

    /**
 * 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(p->val != q->val)
        return false;

        return isSameTree(p->left,q->left) && isSameTree(p->right,q->right);
}

bool isSubtree(struct TreeNode* root, struct TreeNode* subRoot){
    if(root == NULL)
        return false;

    if(isSameTree(root,subRoot))
        return true;
    
    return isSubtree(root->left,subRoot) || isSubtree(root->right,subRoot);
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29

    7. 总结🚀

    通过这几道的简单训练，算是对二叉树的一点巩固，难度大的题目将会在后续。

  • 相关阅读:
    2023.9.7 关于 TCP / IP 的基本认知
    2023年中国牙线市场规模、竞争现状及行业需求前景分析[图]
    2022年陕西省职称申报最全指南
    递归编程练习——北京林业大学
    算法-具有所有最深节点的最小子树(Kotlin)
    多线程案例(单例、阻塞队列、生消模型、定时器)
    【无标题】
    卷积神经网络（CNN）
    关于openfeign的http和rpc
    《OpenDRIVE1.6规格文档》1
  • 原文地址：https://blog.csdn.net/NEFUT/article/details/126831293