# 利用二叉树的先序和中序（中序和后序）排列构建二叉树

https://leetcode.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/

### Construct Binary Tree from Preorder and Inorder Traversal

Total Accepted: 35628 Total
Submissions: 134968My Submissions

Question
Solution

Given preorder and inorder traversal of a tree, construct the binary tree.

Note:

You may assume that duplicates do not exist in the tree.

```/**
* Definition for a binary tree node.
* struct TreeNode {
*     int val;
*     TreeNode *left;
*     TreeNode *right;
*     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
TreeNode* buildhelp(vector<int>& preorder, vector<int>& inorder,int pStart,int pEnd,int iStart,int iEnd){
if(pStart>pEnd||iStart>iEnd)
return NULL;
TreeNode *Tnode=new TreeNode(preorder[pStart]);
if(pStart==pEnd)
return Tnode;
int cur=iStart;
while(inorder[cur]!=preorder[pStart])
cur++;
Tnode->left=buildhelp(preorder, inorder,pStart+1,pStart+(cur-iStart),iStart,cur-1);
Tnode->right=buildhelp(preorder, inorder,pEnd-(iEnd-cur-1),pEnd,cur+1,iEnd);
return Tnode;
}
TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
TreeNode* Tree=NULL;
if(preorder.size()==0)
return Tree;
Tree=buildhelp(preorder, inorder,0,preorder.size()-1,0,inorder.size()-1);
return Tree;
}
};```

```/**
* Definition for a binary tree node.
* struct TreeNode {
*     int val;
*     TreeNode *left;
*     TreeNode *right;
*     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
TreeNode* buildhelp(vector<int>& preorder, vector<int>& inorder,int pStart,int pEnd,int iStart,int iEnd){
if(pStart<pEnd||iStart<iEnd)
return NULL;
TreeNode Tnode(preorder[pStart]);
if(pStart==pEnd)
return &Tnode;
int cur=iStart;
while(inorder[cur]!=preorder[pStart])
cur++;
Tnode.left=buildhelp(preorder, inorder,pStart+1,pStart+(cur-iStart),iStart,cur-1);
Tnode.right=buildhelp(preorder, inorder,pEnd-(iEnd-cur-1),pEnd,cur+1,iEnd);
return &Tnode;
}
TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
TreeNode* Tree=NULL;
if(preorder.size()==0)
return Tree;
Tree=buildhelp(preorder, inorder,0,preorder.size()-1,0,inorder.size()-1);
return Tree;
}
};```

`  TreeNode Tnode(preorder[pStart]);`

```#include<iostream>
#include<vector>
using namespace std;
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

int main()
{
int i=5;
while(i--)
{
TreeNode aa(i);
cout<<&aa<<endl;
}

}```

### Construct Binary Tree from Inorder and Postorder Traversal

Total Accepted: 32565 Total
Submissions: 121341My Submissions

Question
Solution

Given inorder and postorder traversal of a tree, construct the binary tree.

Note:

You may assume that duplicates do not exist in the tree.

```/**
* Definition for a binary tree node.
* struct TreeNode {
*     int val;
*     TreeNode *left;
*     TreeNode *right;
*     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:

TreeNode* buildhelp(vector<int>& inorder, vector<int>& postorder,int iStart,int iEnd,int pStart,int pEnd){
if(pStart>pEnd||iStart>iEnd)
return NULL;
TreeNode Tnode(postorder[pEnd]);
if(pStart==pEnd)
return &Tnode;
int cur=iStart;
while(inorder[cur]!=postorder[pEnd])
cur++;
Tnode.left=buildhelp(inorder, postorder,iStart,cur-1,pStart,pStart+(cur-iStart-1));
Tnode.right=buildhelp(inorder, postorder,cur+1,iEnd,pEnd-1-(iEnd-cur-1),pEnd-1);
return &Tnode;
}
TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
if(inorder.size()==0)
return NULL;
return buildhelp(inorder, postorder,0,inorder.size()-1,0,postorder.size()-1);
}
};```

## 二叉查找树中由前序转化为后序

1 void getPostFromPre(int preL, int preR) { 2 if (preL > preR) return; 3 int i = preL + 1, j = preR; 4 while (i <= preR && pre[i] < pre[preL]) i++; 5 while (j > preL&&pre[j] >= pre[preL]) j--; 6 7 if (i - j != 1) return; 8 g

## 二叉树的前序、中序、后序遍历的递归和非递归算法实现

1 /** 2 * 二叉树的前序.中序.后序遍历的递归和非递归算法实现 3 **/ 4 5 //二叉链表存储 6 struct BTNode 7 { 8 struct BTNode *LChild; // 指向左孩子指针 9 ELEMENTTYPE data; // 结点数据 10 struct BTNode *RChild; // 指向右孩子指针 11 }; 12 13 /** 14 * 前序遍历 15 **/ 16 // 递归实现 17 void PreorderTraversal(BTNo