4、另一颗树的子树
题述：给你两棵二叉树 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
这道题算是 上一篇博客中: 相同的树 的进阶版，如果没有上一题的铺垫，这题会有点难想到。主要思路是判断 二叉树的每一棵子树是否和 subRoot 相等。
由题得，由于 subRoot 一定不为空，所以一旦 root的子树为空，则返回假；
如果 root 的子树 和 subRoot 相等，那么返回真；
否则 递归左右子树，左右子树中任意一边找到了则 子树存在 。
而这里我们判断是否相等就可以直接复用 相同的树 了。
核心思想：每一层函数栈帧中都包括：如果 root 等于空，返回 false；如果调用相同的树为真，返回 true；否则继续递归
//相同的树 bool isSameTree(struct TreeNode* p, struct TreeNode* q) { //p为空，q也为空 if (p == NULL && q == NULL) return true; //p和q只有1个为空 if (p == NULL || q == NULL) return false; //p和q的val不等 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) { //root等于空 if (root == NULL) return false; //调用相同的树 if (isSameTree(root, subRoot)) return true; //继续递归 return isSubtree(root->left, subRoot) || isSubtree(root->right, subRoot); }
5、二叉树遍历
题述：编一个程序，读入用户输入的一串先序遍历字符串，根据此字符串建立一个二叉树（以指针方式存储）。 例如如下的先序遍历字符串： ABC##DE#G##F### 其中“#”表示的是空格，空格字符代表空树。建立起此二叉树以后，再对二叉树进行中序遍历，输出遍历结果。
输入描述：
输入包括1行字符串，长度不超过 100。
输出描述：
可能有多组测试数据，对于每组数据， 输出将输入字符串建立二叉树后中序遍历的序列，每个字符后面都有一个空格。 每个输出结果占一行。
示例 ：
输入：abc##de#g##f###
输出：c b e g d f a
注意此题不同于上面的几道接口题，这里是 I/O 类型的题需要我们自己创建树
根据题意中先序遍历的字符串可以得到：
先前序构建树，再中序输出树
#define _CRT_SECURE_NO_WARNINGS #include<stdio.h> #include<stdlib.h> struct TreeNode { char val; struct TreeNode* left; struct TreeNode* right; }; //前序构建树 struct TreeNode* CreatTree(char* str, int* pi) { if (str[*pi] == '#') { //空树数组的下标也要++，且为它malloc空间 (*pi)++; return NULL; } //malloc空间 struct TreeNode* root = (struct TreeNode*)malloc(sizeof(struct TreeNode)); //前序递归 root->val = str[(*pi)++]; root->left = CreatTree(str, pi); root->right = CreatTree(str, pi); return root; } //中序输出树 void InOrder(struct TreeNode* root) { if (root == NULL) return; InOrder(root->left); printf("%c ", root->val); InOrder(root->right); } int main() { char str[100]; scanf("%s", str); int i = 0; struct TreeNode* root = CreatTree(str, &i); InOrder(root); return 0; }
6、平衡二叉树
描述：给定一个二叉树，判断它是否是高度平衡的二叉树。
本题中，一棵高度平衡二叉树定义为：
一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1 。
示例1：
输入：root = [3,9,20,null,null,15,7]
输出：true
示例2：
输入：root = [1,2,2,3,3,null,null,4,4]
输出：false
示例3：
输入：root = []
输出：true
提示：
树中的节点数在范围 [0, 5000] 内
-104 <= Node.val <= 104
思路：
所谓 平衡二叉树就是任意节点的子树的高度差都小于等于1。
基于这个理解，那么我们可以将它分成：每个节点的子树的高度差小于等于1。
那么：
如果节点为空，则是完全二叉树；如果不为空，就求左右两边子树高度；
再判断左右子树的 高度差的绝对值 是否 大于1 ，大于1则一定不是完全二叉树，返回假；
最后分别递归左右子树，判断左右子树是否满足完全二叉树的条件。
求高度可以使用上上篇博客的 计算二叉树的高度 的接口。
//求二叉树的高度 int TreeHeight(struct TreeNode* root) { if (root == NULL) { return 0; } int leftHeight = TreeHeight(root->left); int rightHeight = TreeHeight(root->right); return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1; } bool isBalanced(struct TreeNode* root) { // 根节点为空，是完全二叉树 if (root == NULL) { return true; } // 求左右两边高度 int leftHeight = TreeHeight(root->left); int rightHeight = TreeHeight(root->right); // 绝对值大于1一定不是完全二叉树 if (abs(leftHeight - rightHeight) > 1) { return false; } return isBalanced(root->left) && isBalanced(root->right); }
总结：
今天我们完成了二叉树OJ题(二)，通过分析明白了思路和原理，愿这篇博客能帮助大家理解这些OJ题，到这里，我们的二叉树就暂告一段落啦。接下来将更新排序算法的相关知识点。希望我的文章和讲解能对大家的学习提供一些帮助。
当然，本文仍有许多不足之处，欢迎各位小伙伴们随时私信交流、批评指正！我们下期见~
