二叉树经典OJ练习

个人主页：C++忠实粉丝
欢迎 点赞👍 收藏✨ 留言✉ 加关注💓本文由 C++忠实粉丝 原创

二叉树经典OJ练习

收录于专栏【数据结构初阶】
本专栏旨在分享学习数据结构学习的一点学习笔记，欢迎大家在评论区交流讨论💌

目录

前置说明 

1. 单值二叉树

2. 相同的树

3. 对称二叉树

4. 二叉树的前序遍历

5. 二叉树中序遍历

6. 二叉树的后序遍历

7. 另一颗树的子树

---

前置说明 

这里大家需要有二叉树的一些基础,还不是很了解的宝子们可以点击下方链接进行查看

---数据结构之二叉树的超详细讲解(3)--(二叉树的遍历和操作)-CSDN博客

1. 单值二叉树

Oj链接--965. 单值二叉树 - 力扣（LeetCode）

题目描述:

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

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

示例 1：

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

示例 2：

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

提示：

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

分析:

题目中给定树的节点数范围是 [1, 100],这里我们就不需要额外判断空节点的情况,我们只需要对二叉树进行遍历一遍,如果遇到空节点返回true,如果root左节点或右节点val不等于root->val,返回false,将最后的结果上传,即可得到最终的结果.

代码展示: 

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);
}

核心逻辑

1. 空树检查

   if(root == NULL) return true;

   这里首先检查根节点是否为空。如果根节点为空，则该树被认为是单值二叉树，返回 true。

2. 左子节点值检查

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

   接下来检查左子节点。如果左子节点存在且其值与根节点的值不相同，则该树不是单值二叉树，返回 false。

3. 右子节点值检查

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

   同样地，检查右子节点。如果右子节点存在且其值与根节点的值不相同，则该树不是单值二叉树，返回 false。

4. 递归检查子树

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

   如果当前节点及其直接子节点都满足条件，则递归检查左子树和右子树。只有在左右子树都是单值二叉树的情况下，当前树才是单值二叉树。

总结

该函数通过递归检查每个节点及其子节点的值是否与根节点的值相同来判断整个二叉树是否是单值二叉树。如果某个节点的值与其父节点不同，立即返回 false。否则，继续递归检查其子树，最终返回整个树的结果。

2. 相同的树

OJ链接--100. 相同的树 - 力扣（LeetCode）

题目描述:

给你两棵二叉树的根节点 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] 内
• -104 <= Node.val <= 104

分析:

两棵树上的节点数目都在范围 [0, 100] 内,说明这里需要进行空树的判断,我们需要先进行判断,当两棵树节点都为空时,满足条件,返回true.当两个节点只有一个为空时,不满足条件,返回false.当两个节点都不为空时,比较两个节点的val,不相等返回false.然后递归遍历两棵树.

代码展示:

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);
}

1. 首先检查 p 和 q 是否同时为 NULL，如果是，说明两棵树都为空，返回 true。
2. 然后检查 p 和 q 是否其中一个为 NULL，另一个不是。如果是，说明两棵树中的节点个数不同，返回 false。
3. 接着检查 p 和 q 的当前节点值是否相同，如果不同，返回 false。
4. 最后，通过递归调用 isSameTree 函数比较两棵树的左子树和右子树是否相同，如果均相同则返回 true，否则返回 false。

这段代码非常简洁而且有效地比较了两棵树是否相同。它利用了递归的特性，逐层比较树的节点值以及对应的子树，从而判断两棵树是否相同。

3. 对称二叉树

OJ链接--101. 对称二叉树 - 力扣（LeetCode）

题目描述:

给你一个二叉树的根节点 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

代码展示:

bool check(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 check(p->left, q->right) && check(p->right, q->left);elsereturn false;
}bool isSymmetric(struct TreeNode* root) {return check(root, root);
}

分析: 

• check 函数：

  • 首先检查 p 和 q 是否同时为 NULL，如果是，说明两个节点都为空，返回 true。
  • 然后检查 p 和 q 是否其中一个为 NULL，另一个不是。如果是，说明两个节点中的一个为空，另一个不为空，返回 false。
  • 接着检查 p 和 q 的值是否相等，如果相等，则递归地比较 p 的左子树和 q 的右子树，以及 p 的右子树和 q 的左子树是否对称。如果均对称，则返回 true，否则返回 false。

• isSymmetric 函数：

  • 调用 check 函数，并传入根节点的左右子树作为参数进行比较。

这段代码利用递归的方式判断了一棵二叉树是否对称。它通过比较树的左右子树是否镜像对称来判断整棵树是否对称。整体上，这段代码实现了一个简洁而有效的对称性判断算法。

函数递归展开图:

4. 二叉树的前序遍历

OJ链接--144. 二叉树的前序遍历 - 力扣（LeetCode）

题目描述:

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

示例 1：

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

示例 2：

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

示例 3：

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

示例 4：

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

示例 5：

输入：root = [1,null,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* preorderTraversal(struct TreeNode* root, int* returnSize) {}

这里我们需要返回的是前序遍历好的数组,而且需要我们自己malloc创建.函数的参数一个是根节点一个是节点个数,要我们实现的是一个输出型函数.

代码展示: 

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

这段代码是关于二叉树前序遍历的实现，其中包括了计算二叉树节点总数和返回前序遍历结果的功能。让我们对这段代码进行详细分析：

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

这部分代码是计算二叉树节点总数的函数 TreeSize，使用了递归的方式来统计节点数量。在每个节点上，它会递归地调用自身来计算左子树和右子树的节点数，并加上当前节点。

void preOrder(struct TreeNode* root, int* a, int* pi) { if(root == NULL) return; a[(*pi)++] = root->val; preOrder(root->left, a, pi); preOrder(root->right, a, pi); }

这部分代码是实现前序遍历的函数 preOrder，它将遍历得到的节点值存储在数组 a 中，使用指针 pi 来跟踪数组的索引位置。

int* preorderTraversal(struct TreeNode* root, int* returnSize) { *returnSize = TreeSize(root); int* a = (int*)malloc(sizeof(int)*(*returnSize)); int i = 0; preOrder(root, a, &i); return a; }

最后，preorderTraversal 函数整合了前两部分的功能。它先计算二叉树的节点总数，然后动态分配一个数组 a 来存储前序遍历的结果，并调用 preOrder 函数来填充数组。最终将数组返回。

总结

这段代码实现了计算二叉树节点总数并返回其前序遍历结果的功能。通过递归的方式遍历二叉树，将节点值按前序遍历顺序存储在数组中，并返回该数组。这样的实现使得我们能够方便地获取二叉树的前序遍历结果，并且能够有效地处理动态分配内存以存储结果。

5. 二叉树中序遍历

OJ链接--94. 二叉树的中序遍历 - 力扣（LeetCode）

题目描述:

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

示例 1：

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

示例 2：

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

示例 3：

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

提示：

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

后面的中序和后序跟前序相差不大,这里就不过多解释. 

代码展示:

int TreeSize(struct TreeNode* root)
{return root == NULL ? 0 : 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;inOrder(root->right,a,pi);
}int* inorderTraversal(struct TreeNode* root, int* returnSize) {*returnSize = TreeSize(root);int* a = (int*)malloc(sizeof(int)*(*returnSize));int i = 0;inOrder(root,a,&i);return a;
}

6. 二叉树的后序遍历

OJ链接--145. 二叉树的后序遍历 - 力扣（LeetCode）

题目描述:

给你一棵二叉树的根节点 root ，返回其节点值的 后序遍历 。

示例 1：

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

示例 2：

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

示例 3：

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

提示：

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

代码展示:

int TreeSize(struct TreeNode* root)
{return root == NULL ? 0 : TreeSize(root->left) + TreeSize(root->right) + 1;
}void postOrder(struct TreeNode* root, int* a, int* pi)
{if(root == NULL)return;postOrder(root->left, a, pi);postOrder(root->right, a, pi);a[(*pi)++] = root->val;
}int* postorderTraversal(struct TreeNode* root, int* returnSize) {*returnSize = TreeSize(root);int* a = (int*)malloc(sizeof(int)*(*returnSize));int i = 0;postOrder(root, a, &i);return a;
}

7. 另一颗树的子树

OJ链接--572. 另一棵树的子树 - 力扣（LeetCode）

题目描述:

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

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

示例 1：

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

示例 2：

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

提示：

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

分析:

遍历root树,找到root的所有子树与subroot树进行比较

代码展示:

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(root->val == subRoot->val && isSameTree(root, subRoot))return true;return isSubtree(root->left,subRoot) || isSubtree(root->right, subRoot);
}

注意:这里需要用到我们之前已经解决的相同的树的问题

该函数用来判断二叉树 subRoot 是否是二叉树 root 的子树。

逻辑解释

1. 空树检查

   if(root == NULL) return false;

   如果 root 是空树，直接返回 false，因为空树不可能包含任何非空子树。

2. 根节点值比较及完整树比较

   if(root->val == subRoot->val && isSameTree(root, subRoot)) return true;

   如果 root 的当前节点值与 subRoot 的根节点值相同，并且 root 从当前节点开始的子树与 subRoot 完全相同（通过调用 isSameTree 函数进行判断），则返回 true。

3. 递归检查左右子树

   return isSubtree(root->left, subRoot) || isSubtree(root->right, subRoot);

   如果上述条件都不满足，则递归地检查 root 的左子树和右子树，看其中是否存在与 subRoot 相同的子树。如果任意一个子树包含 subRoot，返回 true。

总结

这两个函数结合起来可以有效地判断一棵二叉树是否是另一棵二叉树的子树。具体步骤如下：

1. 使用 isSubtree 函数遍历 root 的每个节点。
2. 对于每个节点，检查该节点开始的子树是否与 subRoot 完全相同。
3. 如果找到一个与 subRoot 相同的子树，立即返回 true。
4. 如果没有找到，继续遍历 root 的左右子树，直到所有节点都检查完毕。

这种方法通过递归遍历和子树比较，确保准确判断子树关系。