1.另一棵树的子树

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

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

力扣https://leetcode.cn/problems/subtree-of-another-tree/

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

这道题是下面这个题的进阶版

力扣https://leetcode.cn/problems/same-tree/

这段代码是用来判断一棵树是否是另一棵树的子树。函数 isSameTree() 是用来判断两棵树是否相同，函数 isSubtree() 则是通过不断递归左右子树来判断是否为子树。

具体实现思路如下：

• 如果根节点为空，则肯定不存在子树，返回 false。
• 如果当前根节点与子树的根节点相同，则直接调用 isSameTree() 函数来比较它们是否完全相同，如果相同则说明找到了子树，返回 true。
• 如果当前根节点与子树的根节点不同，那么继续递归查找左右子树，并将两者的结果进行逻辑或运算，若其中一个为 true，说明找到了子树，返回 true，否则返回 false。

函数 isSameTree() 判断两棵树是否相同的实现思路如下：

• 如果两棵树都为空，则认为它们相同，返回 true。
• 如果其中有一棵树为空，另一棵树不为空，则认为它们不相同，返回 false。
• 如果两棵树的根节点值不相同，则认为它们不相同，返回 false。
• 如果两棵树的根节点值相同，则递归地比较它们的左右子树，只有左右子树都相同，才认为这两棵树相同，否则返回 false。

总体上，这个算法的时间复杂度是 O(nm)，其中 n 是原树的节点数，m 是子树的节点数。空间复杂度为 O(max(n,m))，即递归深度。这个算法利用了树的递归结构，通过不断地递归查找子树来判断是否存在子树，因此实现相对简单，但是时间复杂度较高。

2.二叉树遍历

描述

编一个程序，读入用户输入的一串先序遍历字符串，根据此字符串建立一个二叉树（以指针方式存储）。 例如如下的先序遍历字符串： ABC##DE#G##F 其中“#”表示的是空格，空格字符代表空树。建立起此二叉树以后，再对二叉树进行中序遍历，输出遍历结果。

输入描述：

输入包括1行字符串，长度不超过100。

输出描述：

可能有多组测试数据，对于每组数据， 输出将输入字符串建立二叉树后中序遍历的序列，每个字符后面都有一个空格。 每个输出结果占一行。

 二叉树遍历_牛客题霸_牛客网【牛客题霸】收集各企业高频校招笔面试题目，配有官方题解，在线进行百度阿里腾讯网易等互联网名企笔试面试模拟考试练习,和牛人一起讨论经典试题,全面提升你的技术能力https://www.nowcoder.com/practice/4b91205483694f449f94c179883c1fef?tpId=60&&tqId=29483&rp=1&ru=/activity/oj&qru=/ta/tsing-kaoyan/question-ranking

#include <stdio.h>struct TreeNode{struct TreeNode*left;struct TreeNode*right;char val;
};struct TreeNode*CreateTree(char*a,int* pi)
{if(a[*pi]=='#'){(*pi)++;return NULL;}struct TreeNode*root=(struct TreeNode*)malloc(sizeof(struct TreeNode));root->val=a[(*pi)++];root->left=CreateTree(a,pi);root->right=CreateTree(a,pi);return root;
}void inOrder(struct TreeNode*root)
{if(root==NULL)return;inOrder(root->left);printf("%c ",root->val);inOrder(root->right);
}void DestroyTree(struct TreeNode* root){if(root == NULL)return;DestroyTree(root->left);DestroyTree(root->right);free(root);
}int main() {char a[100];scanf("%s",a);int i=0;struct TreeNode*root=CreateTree(a, &i);inOrder(root);DestroyTree(root);return 0;
}

这段代码是在 C 语言中使用递归算法实现二叉树的先序遍历和销毁。其中 CreateTree 函数用于根据输入的字符串构建二叉树，每次递归调用 CreateTree 函数时，都从字符数组 a 中读取一个字符，并根据该字符构建根节点，然后递归创建左子树和右子树，直到遇到结束标识符 '#'，返回 NULL 结束递归。

inOrder 函数用于进行中序遍历，其思路和 CreateTree 函数类似，也是先递归访问左子树，再访问根节点，最后递归访问右子树。

DestroyTree 函数用于释放二叉树占用的内存空间。它首先递归地销毁左子树和右子树，然后释放根节点所占用的内存空间。这样可以保证在程序结束时，完全释放二叉树所占用的内存空间，避免出现内存泄露的问题。

在 main 函数中，首先读入一个输入字符串，然后调用 CreateTree 函数构建二叉树，使用 inOrder 函数进行中序遍历，最后调用 DestroyTree 函数释放内存空间，结束程序的执行