文章目录

• 前言
• 💎一、题目一
• • 🏆1.题目描述
  • 🏆2.解题思路
  • 🏆3.代码详解
• 💎二、题目二
• • 🏆1.题目描述
  • 🏆2.解题思路
  • 🏆3.代码详解
• 💎三、题目三
• • 🏆1.题目描述
  • 🏆2.解题思路
  • 🏆3.代码详解
• 💎四、题目四
• • 🏆1.题目描述
  • 🏆2.解题思路
  • 🏆3.代码详解
• 💎五、星球推荐

前言

        树是一种数据结构，它是由n(n≥0)个有限节点组成一个具有层次关系的集合。把它叫做“树”是因为它看起来像一棵倒挂的树，也就是说它是根朝上，而叶朝下的。它具有以下的特点：
        每个节点有零个或多个子节点；没有父节点的节点称为根节点；每一个非根节点有且只有一个父节点；除了根节点外，每个子节点可以分为多个不相交的子树。
刷题坚持每一天，以下题目引用自：力扣（LeetCode）

💎一、题目一

🏆1.题目描述

原题链接：2236. 判断根结点是否等于子结点之和

        给你一个 二叉树 的根结点 root，该二叉树由恰好 3 个结点组成：根结点、左子结点和右子结点。
如果根结点值等于两个子结点值之和，返回 true ，否则返回 false 。

示例 1：

输入：root = [10,4,6]
输出：true
解释：根结点、左子结点和右子结点的值分别是 10 、4 和 6 。
由于 10 等于 4 + 6 ，因此返回 true 。

🏆2.解题思路

🔑思路：

​         对根节点与子节点的和比较是否相等。

🏆3.代码详解

bool checkTree(struct TreeNode* root){    return root->val == root->left->val+root->right->val;}

💎二、题目二

🏆1.题目描述

原题链接：面试题 04.10. 检查子树

        检查子树。你有两棵非常大的二叉树：T1，有几万个节点；T2，有几万个节点。设计一个算法，判断 T2 是否为 T1 的子树。
        如果 T1 有这么一个节点 n，其子树与 T2 一模一样，则 T2 为 T1 的子树，也就是说，从节点 n 处把树砍断，得到的树与 T2 完全相同。

示例 1：
输入：t1 = [1, 2, 3], t2 = [2]
输出：true

🏆2.解题思路

🔑思路：

​         后序遍历+hash，把每一个节点下的子节点处理加一块赋给这个节点，给出的子树相同操作。把t1的每个节点值与t2的根节点值进行判断是否相等。

🏆3.代码详解

void Postorderhash(struct TreeNode* root){    if(root == NULL) return;    Postorderhash(root->left);    Postorderhash(root->right);    unsigned int le = root->left ? root->left->val : 123;    unsigned int ri = root->right ? root->right->val : 789;    root->val = (root->val + le + ri) % 100000001;}bool find(struct TreeNode* root, int value){    if(root == NULL) return false;    return root->val == value || find(root->left, value) || find(root->right, value);}bool checkSubTree(struct TreeNode* t1, struct TreeNode* t2){    if(!t2) return true;    Postorderhash(t1);    Postorderhash(t2);    return find(t1, t2->val);}

💎三、题目三

🏆1.题目描述

原题链接：面试题 04.06. 后继者

        设计一个算法，找出二叉搜索树中指定节点的“下一个”节点（也即中序后继）。
如果指定节点没有对应的“下一个”节点，则返回null。

示例 1：
输入: root = [2,1,3], p = 1
    2
  /   \
1    3
输出: 2

🏆2.解题思路

🔑思路：

​        中序遍历，找到与p相等的值后，取下一个不为空的节点值。

🏆3.代码详解

bool flag = false;struct TreeNode* ret = NULL;void Inorder(struct TreeNode* root, struct TreeNode* p){    if(root == NULL) return;    Inorder(root->left, p);     if(flag && ret == NULL){ ret = root; return;    }    if(root == p) flag = true;    Inorder(root->right, p);}struct TreeNode* inorderSuccessor(struct TreeNode* root, struct TreeNode* p){     flag = false;     ret = NULL;     Inorder(root, p);     return ret;}

💎四、题目四

🏆1.题目描述

原题链接：1110. 删点成林

        给出二叉树的根节点 root，树上每个节点都有一个不同的值。
如果节点值在 to_delete 中出现，我们就把该节点从树上删去，最后得到一个森林（一些不相交的树构成的集合）。
返回森林中的每棵树。你可以按任意顺序组织答案。

示例 1：

输入：root = [1,2,3,4,5,6,7], to_delete = [3,5]
输出：[[1,2,null,4],[6],[7]]

🏆2.解题思路

🔑思路：

​         遍历到需要删除的父节点，把下面的孩子节点链接置空，并把孩子节点链接放入结果数组。

🏆3.代码详解

int count = 0;void Postorder(struct TreeNode* parent, struct TreeNode* root, struct TreeNode** ret, int flag, int* hash){    if(root == NULL) return;    Postorder(root, root->left, ret, true, hash);    Postorder(root, root->right, ret, false, hash); if(hash[root->val]){ if(parent){     if(flag) parent->left = NULL;     else parent->right = NULL; } if(root->left) ret[count++] = root->left; if(root->right) ret[count++] = root->right;    }}struct TreeNode** delNodes(struct TreeNode* root, int* to_delete, int to_deleteSize, int* returnSize){    if(root == NULL) return;    int hash[1001];    struct TreeNode** ans = (struct TreeNode**)malloc(sizeof(struct TreeNode*)*1001);    memset(hash, 0, sizeof(hash)); for(int i = 0; i < to_deleteSize; ++i){ hash[to_delete[i]] = 1;    }    count = 0;    Postorder(NULL, root, ans, false, hash); if(hash[root->val] == 0) ans[count++] = root;    * returnSize = count;    return ans;}

💎五、星球推荐

        星球链接：英雄算法联盟

星球里有什么?
        【朋友圈】一个极致精准的自律、编程、算法的小圈子。
        【算法集训】以月为单位组织算法集训，每天四题，风雨无阻。
        【排行榜】每天、每周都会有榜单，激励大家不断进步，不断成长。
        【个人规划】每个人都写好自己的规划，也可以查看他人的规划，时刻警醒自己不掉队。
        【打卡挑战】每日一题打卡、每日早起打卡、算法集训打卡、规划完成情况打卡。
在星球里做什么?
        目前星球人数达到420+，在星球里你能够遇到一群志同道合之人，因为都是花钱进来的，你不会看到任何浑水摸鱼的人，每个人都有自己的每月规划，星主每月都会组织算法集训，每天一起刷题，你可以看到别人的解题报告，取其之长，补己之短。