《算法笔记》树与二叉树专题练习中，有哪些长尾词技巧和算法应用？

本文共计1298个文字，预计阅读时间需要6分钟。

给定一棵二叉树的前序遍历和后序遍历结果，要求输出这棵二叉树的后序遍历结果。

解题思路：

1.根据前序遍历和后序遍历的结果，确定二叉树的根节点。

2.在前序遍历中找到根节点之后的部分，即为左子树的前序遍历结果。

3.在后序遍历中找到根节点之前的部分，即为右子树的后序遍历结果。

4.递归地对左子树和右子树进行上述步骤，直到所有节点都被处理。

具体步骤：

1.初始化一个空列表`postorder`作为后序遍历结果。

2.如果前序遍历或后序遍历为空，直接返回`postorder`。

3.取出前序遍历的第一个元素作为根节点。

4.在后序遍历中找到根节点的位置，得到右子树的后序遍历结果。

5.在前序遍历中找到根节点之后的部分，得到左子树的前序遍历结果。

6.递归地对左子树和右子树执行步骤1-6。

7.将根节点添加到`postorder`中。

8.返回`postorder`。

代码实现：

python

def postorder_traversal(preorder, inorder): if not preorder or not inorder: return []

root=preorder[0] root_index=inorder.index(root)

left_inorder=inorder[:root_index] right_inorder=inorder[root_index+1:]

left_preorder=preorder[1:1+len(left_inorder)] right_preorder=preorder[1+len(left_inorder):]

left_postorder=postorder_traversal(left_preorder, left_inorder) right_postorder=postorder_traversal(right_preorder, right_inorder)

return left_postorder + right_postorder + [root]

示例preorder=[3, 9, 20, 15, 7]inorder=[9, 3, 15, 20, 7]print(postorder_traversal(preorder, inorder))

输出结果：[9, 15, 7, 3, 20]

1、复原二叉树（由前序和中序求后序）

题目描述 小明在做数据结构的作业，其中一题是给你一棵二叉树的前序遍历和中序遍历结果，要求你写出这棵二叉树的后序遍历结果。 输入 输入包含多组测试数据。每组输入包含两个字符串，分别表示二叉树的前序遍历和中序遍历结果。每个字符串由不重复的大写字母组成。 输出 对于每组输入，输出对应的二叉树的后续遍历结果。

DBACEGF ABCDEFG BCAD CBAD ACBFGED CDAB

#include <iostream> #include<cstring> using namespace std; const int maxN=1000; //分别存储前序序列、中序序列 char pre[maxN],in[maxN]; struct Node { char data; Node* lchild; Node* rchild; }; //根据前序序列和中序序列构建一棵二叉树 Node* create(int preL,int preR,int inL,int inR) { if(preL>preR)return NULL;//递归边界，前序序列长度小于等于0时结束 Node* root=new Node;//创建根节点 root->data=pre[preL];//先序序列的第一个就是根节点 int k; for(k=inL;k<=inR;k++) { if(in[k]==pre[preL])break;//找到根节点在中序序列中的位置 } int numLeft=k-inL;//左子树的节点个数 //注意区间 root->lchild=create(preL+1,preL+numLeft,inL,k-1); root->rchild=create(preL+numLeft+1,preR,k+1,inR); return root; } //二叉树的后序遍历，左右根顺序 void postOrder(Node* root) { if(root==NULL)return; postOrder(root->lchild); postOrder(root->rchild); printf("%c",root->data); } int main() { while(scanf("%s%s",pre,in)!=EOF) { int preLen=strlen(pre); int inLen=strlen(in); Node* root=create(0,preLen-1,0,inLen-1); postOrder(root); printf("\n"); } return 0; }

2、二叉树遍历

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

输入

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

输出

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

a#b#cdef##### a## a b f e d c a

#include<iostream> #include<cstring> using namespace std; char pre[105]; int pos; struct Node { char data; Node* lchild; Node* rchild; }; //创建空节点 Node* createNode() { Node* node=new Node; node->lchild=NULL; node->rchild=NULL; return node; } //创建二叉树 Node* createTree() { int len=strlen(pre); if(len==0||pos==len)return NULL;//数据为空或已经遍历完 if(pre[pos]=='#')//空树，直接遍历下一个，然后返回空 { pos++; return NULL; } Node* root=createNode();//先创建一个根节点 root->data=pre[pos++]; //递归创建左右子树 root->lchild=createTree(); root->rchild=createTree(); return root; } //二叉树的中序遍历，左根右顺序 void inOrder(Node* root) { if(root==NULL)return; inOrder(root->lchild); printf("%c ",root->data); inOrder(root->rchild); } int main() { while(scanf("%s",pre)!=EOF) { pos=0; Node* root=createTree(); inOrder(root); printf("\n"); } return 0; }