6. 二叉树的后序遍历
链接：https://leetcode-cn.com/problems/binary-tree-postorder-traversal/
int TreeSize(struct TreeNode* root) { return root == NULL ? 0 : TreeSize(root->left)+TreeSize(root->right) + 1; } void _postorderTraversal(struct TreeNode* root,int* a,int* pi) { if(root == NULL) { return; } _postorderTraversal(root->left, a, pi);//左 _postorderTraversal(root->right, a, pi);//右 a[(*pi)++] = root->val;//根 } int* postorderTraversal(struct TreeNode* root, int* returnSize){ int size = TreeSize(root); int* a = malloc(sizeof(int) * size); int i = 0; _postorderTraversal(root, a, &i); *returnSize = size; return a; }
7. 另一棵子树
链接：https://leetcode-cn.com/problems/subtree-of-another-tree
给你两棵二叉树 root 和 subRoot 。检验 root 中是否包含和 subRoot 具有相同结构和节点值的子树。如果存在，返回 true ；否则，返回 false 。二叉树 tree 的一棵子树包括 tree 的某个节点和这个节点的所有后代节点。tree 也可以看做它自身的一棵子树。
思路：让root的每棵子树与subroot相比较 （和第3题有些类似，判断相同的树）
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; } //root的左子树与subroot比较 和 root的右子树与subroot比较 只要有一个相同就是满足条件的 return isSubtree(root->left,subRoot) || isSubtree(root->right,subRoot); }
8. 二叉树遍历
这是一道牛客网得到题目：
描述：
编一个程序，读入用户输入的一串先序遍历字符串，根据此字符串建立一个二叉树（以指针方式存储）。 例如如下的先序遍历字符串： ABC##DE#G##F### 其中“#”表示的是空格，空格字符代表空树。建立起此二叉树以后，再对二叉树进行中序遍历，输出遍历结果。
输入描述：
输入包括1行字符串，长度不超过100。
输出描述：
可能有多组测试数据，对于每组数据， 输出将输入字符串建立二叉树后中序遍历的序列，每个字符后面都有一个空格。 每个输出结果占一行。
示例：
输入：a b c # # d e # g # # f # # #
输出：c b e g d f a
思路：
本题的关键点时如何让用户输入的字符串是先序遍历（即前序遍历），我们利用前序遍历的思路去创建每个结点，并将其链接起来；根据题目所给的字符串，是否能画出它的前序遍历结构图，如下所示：
动图演示：
#include <stdio.h> #include <stdlib.h> struct TreeNode { char val; struct TreeNode* left; struct TreeNode* right; }; struct TreeNode* CreateTree(char* str,int* pi) { //遇到‘#’号就跳过去 if(str[*pi] == '#') { (*pi)++; return NULL; } struct TreeNode* root = (struct TreeNode*)malloc(sizeof(struct TreeNode)); root->val = str[*pi];//先创建根 (*pi)++; root->left = CreateTree(str,pi);//再创建左子树 root->right = CreateTree(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 = CreateTree(str,&i); Inorder(root); return 0; }
