KY11 二叉树遍历
题目来源:二叉树遍历_牛客题霸_牛客网 (nowcoder.com)
题目描述:
编一个程序，读入用户输入的一串先序遍历字符串，根据此字符串建立一个二叉树（以指针方式存储）。 例如如下的先序遍历字符串： ABC##DE#G##F### 其中“#”表示的是空格，空格字符代表空树。建立起此二叉树以后，再对二叉树进行中序遍历，输出遍历结果。
输入描述:
输入包括1行字符串，长度不超过100。
输出描述:
可能有多组测试数据，对于每组数据， 输出将输入字符串建立二叉树后中序遍历的序列，每个字符后面都有一个空格。 每个输出结果占一行。
示例1
输入:abc##de#g##f### 输出:c b e g d f a
解题思路:
先来复习一遍前序遍历，在此基础上，遍历一个比较难的字符串。
画出其前序遍历图：
画出其前序遍历递归图(省略一部分同理的)，剩下的可以根据上面的前序遍历图可求出
有了上面的基础，我们写出代码实现部分：
typedef int BTDataType; typedef struct BTreeNode { int val; struct BTreeNode* left; struct BTreeNode* right; }BTNode; BTNode* BuyNode(BTDataType x) { BTNode* root=(BTNode*)malloc(sizeof(BTNode)); if(root == NULL) { perror("malloc fail"); return NULL; } root->val=x; root->left =NULL; root->right = NULL; return root; } BTNode* CreateTree(char* a,int* pi) { if(a[(*pi)] =='#') { (*pi)++; return NULL; } BTNode* root = BuyNode(a[(*pi)]); (*pi)++; root->left = CreateTree(a, pi); root->right = CreateTree(a,pi); return root; } void InOrder(BTNode* root) { if(root == NULL) { return ; } InOrder(root->left); printf("%c ",root->val); InOrder(root->right); } int main() { char a[100]; scanf("%s",a); int i=0; BTNode* root=CreateTree(a,&i); InOrder(root); printf("\n"); }
执行：
leetcode 94.二叉树中序遍历(数组存储)
题目来源:94. 二叉树的中序遍历 - 力扣（LeetCode）
题目描述：
给定一个二叉树的根节点 root ，返回 它的 中序 遍历 。
示例:
解题思路:
跟上一篇的前序遍历相差不大，就是将参数换个位置，其它不便说明。
代码实现：
int TreeSize(struct TreeNode* root) { if(root == NULL) { return 0; } return 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(*returnSize *sizeof(int)); int i=0; _inorder(root,a,&i); return a; }
代码执行：
leetcode 145二叉树的后序遍历(数组存储)
题目来源：145. 二叉树的后序遍历 - 力扣（LeetCode）
题目描述：
给你一棵二叉树的根节点 root ，返回其节点值的 后序遍历 。
示例：
解题思路：
跟上一篇的前序遍历相差不大，就是将参数换个位置，其它不便说明。
代码实现：
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(*returnSize*sizeof(struct TreeNode)); int i=0; _postorder(root,a,&i); return a; }
