2022-08-28 20:56 滴滴_C++(准入职员工)

发布于广东

关注

【数据结构与算法】二叉树题目很难？一句话秒杀基础二叉树题目

💛 前情提要💛

本章节是数据结构的链式二叉树的相关知识~

接下来我们即将进入一个全新的空间，对代码有一个全新的视角~

以下的内容一定会让你对数据结构有一个颠覆性的认识哦！！！

❗以下内容以C语言的方式实现，对于数据结构来说最重要的是思想哦❗

以下内容干货满满，跟上步伐吧~

💡本章重点

二叉树链式结构的概念
二叉树的三种遍历方式
🔥算法思想

🍞一.二叉树的概念

🥐Ⅰ.二叉树链式结构

💡简单来说：

就是用链表去表示一棵二叉树，即用链表去表示元素之间的逻辑关系

二叉树链式结构不同于堆【因为堆又称为二叉树的顺序结构】
- 二叉树的链式结构可以存储任意 树（包括：普通二叉树，满二叉树，完全二叉树等）
- 而二叉树的顺序结构存储更多存储的是完全二叉树、满二叉树，而不存储普通二叉树，否则会造成空间浪费

👉二叉树可分两种：

空树
非空树：根节点、根节点的左子树、根节点的右子树组成（如下图：）

👉代码实现：

typedef int BTDataType;

typedef struct BinaryTreeNode
{
    struct BinaryTreeNode* left; 
    struct BinaryTreeNode* right;
    BTDataType data;
}BTNode;

❗综上：

不难发现二叉树的定义正是递归式
所以我们正可以通过递归的方式去遍历整个二叉树

✊所以接下来我们就开始实现吧~

🍞二.二叉树的遍历

🥐Ⅰ.前序遍历

💡前序遍历： 又称为先根遍历

即访问根结点的操作发生在遍历其左右子树之前

简单来说：优先访问根节点，继而访问根节点的左子树，最后再访问根节点的右子树

❗特别注意：

上述所说的根节点不仅仅指的是整棵树的根节点，也指每一个结点【因为每一个结点都可以当作一个根节点来看待】
因此每一个结点都可以以根节点看待【即一棵完整的树，被拆分成多个子树看待】

✊动图示例：

👉代码实现：

void PrevOrder(BTNode* root)
{
    if (root == NULL)
    {
        printf("NULL ");
        return;
    }

    //访问根结点
    printf("%d ", root->data);
    //访问左子树
    PrevOrder(root->left);
    //访问右子树
    PrevOrder(root->right);
}

👆递归展示：

✨综上： 每个结点都可以看作一棵树【即拆分成子问题看待】

每次先访问根结点
继而访问左子树，直至访问完全整棵树中的左子树
最后访问右子树，直至访问完全整棵树中的右子树

🥐Ⅱ.中序遍历

💡前序遍历： 又称为中根遍历

即访问根结点的操作发生在遍历其左右子树之中（间）
- 简单来说：先递归遍历完根节点的左子树，而后递归返回时访问根节点，最后再递归访问根节点的右子树

❗特别注意：

上述所说的根节点不仅仅指的是整棵树的根节点，也指每一个结点【因为每一个结点都可以当作一个根节点来看待】
因此每一个结点都可以以根节点看待【即一棵完整的树，被拆分成多个子树看待】

✊动图示例：

👉代码实现：

void InOrder(BTNode* root)
{
    if (root == NULL)
    {
        printf("NULL ");
        return;
    }

    //访问左子树
    InOrder(root->left);
    //访问根结点
    printf("%d ", root->data);
    //访问右子树
    InOrder(root->right);
}

✨综上： 每个结点都可以看作一棵树【即拆分成子问题看待】

每次先访问左子树，直至访问完全整棵树中的左子树
继而访问根节点
最后访问右子树，直至访问完全整棵树中的右子树

🥐Ⅲ.后序遍历

💡前序遍历： 又称为后根遍历

即访问根结点的操作发生在遍历其左右子树之后

简单来说：优先访问根节点的右子树，继而访问根节点，最后再访问根节点的左子树

❗特别注意：

上述所说的根节点不仅仅指的是整棵树的根节点，也指每一个结点【因为每一个结点都可以当作一个根节点来看待】
因此每一个结点都可以以根节点看待【即一颗完整的树，被拆分成多个子树看待】

✊动图示例：

👉代码实现：

void PostOrder(BTNode* root)
{
    if (root == NULL)
    {
        printf("NULL ");
        return;
    }

    //访问左子树
    PostOrder(root->left);
    //访问右子树
    PostOrder(root->right);
    //访问根结点
    printf("%d ", root->data);
}

✨综上： 每个结点都可以看作一棵树【即拆分成子问题看待】

每次先访问左子树，直至访问完全整棵树中的左子树
继而访问右子树，直至访问完全整棵树中的右子树
最后再访问根结点

🥯Ⅳ.总结

✨综上：三种二叉树的遍历方式，本质就是调换访问左子树、右子树、根节点的语句次序，然后程序便会自动递归帮我们访问完整棵树的所有结点啦~

➡️相信大家对三种遍历方式有不一样的看法了吧🧡

🍞三.二叉树OJ题

🔥秒杀模板

❗ 秒杀口诀：

左右子树之间的逻辑关系➕树的遍历方式
- 1️⃣左右子树之间的关系：指的是为了达到题目要求的结果，我们需要让左、右子树之间达成什么样的关系【Eg：逻辑关系（&&、||、……）、算数关系（+、-、……）、……】
- 2️⃣找出逻辑关系后，只需要结合合适的遍历方式，相当于找到通式，便可以通过通式解决题目了

❓具体是怎么运用呢？

✊让我们用题目来实际运用分析吧~

🏷️ 单值二叉树【难度：简单】

:mag:题目传送门：

Leetcode：965. 单值二叉树

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

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

示例 1：

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

示例 2：

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

💡解题关键：

我们只需要遍历二叉树的每一个结点，一一比较每个结点的值是否相同
本题就可以运用我们的秒杀技巧

👉秒杀分析：

此处先找到左、右子树之间的逻辑关系
- 我们将视角放到整体的树上，只看这个树的左、右子树之间通过怎样的逻辑关系才能实现题目要求（如下：）

➡️如上我们便可发现： 题目需要我们去判断每一个结点的值是否相同，那此时对于上面的树来说，我们就需要判断左子树、右子树里的每一个结点是否与根节点的值相同

1️⃣那此时我们便找到合适的遍历方式：前序遍历

- [ ] <font color = #48B378>因为每次遍历下来直接先判断根节点的值是否相同，不相同就可以直接返回`false`，不再需要递归下去

- [ ] <font color = #48B378>否则，若用其它遍历方式，就需要在判断完子树的所有结点后，返回的时候才判断`根节点`

➡️又因为： 需要左子树与右子树递归判断完后返回的结果都为true后，整棵树才真正的满足单值二叉树

2️⃣那此时我们便知道左、右子树之间的逻辑关系为&&【只有左右俩操作数都满足时，才真正的满足】

👆综上：

秒杀口诀为：&&➕前序遍历
本质：将每个结点与自己的孩子结点进行比较，看是否相同，一直比较直至递归完整棵树【利用的是：等号具有传递性】

❗特别注意：

当根节点或者二叉树为NULL的时候，就返回true，因为没有值的结点可以不参与判断，有值的才去进行判断
在进行每一个结点与孩子结点比较的时候，需要判断提前孩子结点是否为NULL，因为只有不为NULL才能访问到这个结点的val ；否则会造成非法访问内存

✊动图示例：

👉代码实现：

bool isUnivalTree(struct TreeNode* root)
{
    if (root == NULL)
    {
        return true;
    }

    if (root->left && root->left->val != root->val)
    {
        return false;
    }

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

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

➡️补充：

这里设计得也很巧妙，即左子树已经是单值的情况下，才走右子树
否则，若左子树有不相等的情况下，就可以直接不走右子树了

🏷️ 相同的树【难度：简单】

:mag:题目传送门：

Leetcode：100. 相同的树

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

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

示例 1：

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

示例 2：

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

示例三：

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

💡解题关键：

两棵树同时遍历，一一比较是否相同
但这里我们不写相等的递归结束条件，而是写不相等的条件，因为这里即需要判断树的结构也要判断相同结构下相同结点的值相等，所以这里相等的条件不好描述出来
但如果是写当树不相等的条件的话，一旦判断不相等，那一定是不相同的二叉树

👉秒杀分析：

这里的分析和上题的如出一辙，所以我们选择&&➕前序遍历

➡️做题思路：

1️⃣当两棵树都为空树（NULL）or 都比较完前面的结点直至NULL的时候，证明前面判断的每个结点都是相同的，所以返回true
2️⃣通过判断各自树的当前结点是否NULL，从而判断树的结构是否相同，也预防了对NULL 结点的访问
3️⃣判断完结构后，再进行最后的值判断

✊动图示例：

❗特别注意：

上述的动图中看上去是两棵树分开走的，但再代码实现中其实是一起走的
且返回的时候其实是两棵树共同返回的是一个true，上述动图只是为了好表达才这样表示

👉代码实现：

bool isSameTree(struct TreeNode* p, struct TreeNode* q) 
{
    //1.树都为NULL的时候 -- 相等
    //2.比较比到 NULL 的时候 == 前面都比完了，那就相等
    if (p == NULL && q == NULL)
    {
        return true;
    }

    //判断p树和q树结构是否相同
    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);
}

🏷️ 对称二叉树【难度：简单】

:mag:题目传送门：

Leetcode：101. 对称二叉树

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

示例 1：

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

示例 2：

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

💡解题关键：

本题类似于上题，可复用上题的思路
这里的思路是拆分子问题，将一棵树的左、右子树看成两棵树，去复用上题的代码

👉秒杀分析：

这里的分析和上题的如出一辙，所以我们选择&&➕前序遍历

❗特别注意：

当树为空树（NULL），就直接返回true ,因为空树没有结点，本来就是对称的
因为这里判断的是对称，所以：
- 左子树中的左孩子是与右子树中的右孩子比较的
- 左子树中的右孩子是与右子树中的左子树比较的

👉代码实现：

bool _isSymmetric(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  _isSymmetric(left->left, right->right) && _isSymmetric(left->right, right->left);
}

bool isSymmetric(struct TreeNode* root) 
{
    if (root == NULL)
    {
        return true;
    }

    return  _isSymmetric(root->left, root->right);
}