兵团建设环保局网站/网站建设关键词排名

在数据结构中，我们经常需要根据不同的组合遍历顺序确定一个二叉树，并生成它，现在就来整理一下思路，这儿以中序遍历和后序遍历为例！

如上图所示，我们先由于后序遍历找到根结点，然后在中序遍历的序列中找到对应的根结点，此时可以将中序遍历和后续遍历中左右子树的位置确定，然后递归进行划分，注意递归的结束条件的设置！
实现代码如下：

1、给定中序遍历和后序遍历实现：

1）递归结束条件为：i_l>i_r，注意调用时候的参数设置！

class Solution {
public:TreeNode *buildTree(vector<int> &inorder, vector<int> &postorder) {if(inorder.size()==0)return NULL;TreeNode* root=buildTree_(inorder,0,inorder.size()-1,postorder,0,postorder.size()-1);return root;}TreeNode* buildTree_(vector<int>& inorder,int i_l,int i_r,vector<int>& postorder,int p_l,int p_r){if(i_l>i_r) return NULL;TreeNode* root=new TreeNode(postorder[p_r]);int count=0;for(int i=i_l;i<i_r;i++){if(inorder[i]==postorder[p_r]) break;count++;}root->left=buildTree_(inorder,i_l,i_l+count-1,postorder,p_l,p_l+count-1);root->right=buildTree_(inorder,i_l+count+1,i_r,postorder,p_l+count,p_r-1);return root;}
};

2）递归结束条件为：i_l==i_r，注意调用的参数设置！

class Solution {
public:TreeNode *buildTree(vector<int> &inorder, vector<int> &postorder) {if(inorder.size()==0)return NULL;TreeNode* root=buildTree_(inorder,0,inorder.size(),postorder,0,postorder.size());return root;}TreeNode* buildTree_(vector<int>& inorder,int i_l,int i_r,vector<int>& postorder,int p_l,int p_r){if(i_l==i_r) return NULL;TreeNode* root=new TreeNode(postorder[p_r-1]);int count=0;for(int i=i_l;i<i_r;i++){if(inorder[i]==postorder[p_r-1]) break;count++;}root->left=buildTree_(inorder,i_l,i_l+count,postorder,p_l,p_l+count);root->right=buildTree_(inorder,i_l+count+1,i_r,postorder,p_l+count,p_r-1);return root;}
};

2、给定先序遍历和中序遍历实现：

1）递归条件为i_l>i_r时：

class Solution {
public:TreeNode *buildTree(vector<int> &preorder, vector<int> &inorder) {if(preorder.empty()) return NULL;TreeNode* root=buildTree_(preorder,0,preorder.size()-1,inorder,0,inorder.size()-1);return root;}TreeNode* buildTree_(vector<int>& preorder,int p_l,int p_r,vector<int>& inorder,int i_l,int i_r){if(i_l>i_r) return NULL;TreeNode* root=new TreeNode(preorder[p_l]);int count=0;for(int i=i_l;i<=i_r;i++){if(inorder[i]==preorder[p_l]) break;count++;}root->left=buildTree_(preorder,p_l+1,p_l+count,inorder,i_l,i_l+count-1);root->right=buildTree_(preorder,p_l+count+1,p_r,inorder,i_l+1+count,i_r);return root;}
};

2）递归条件为i_l==i_r时：

class Solution {
public:TreeNode *buildTree(vector<int> &preorder, vector<int> &inorder) {if(preorder.empty()) return NULL;TreeNode* root=buildTree_(preorder,0,preorder.size(),inorder,0,inorder.size());return root;}TreeNode* buildTree_(vector<int>& preorder,int p_l,int p_r,vector<int>& inorder,int i_l,int i_r){if(i_l==i_r) return NULL;TreeNode* root=new TreeNode(preorder[p_l]);int count=0;for(int i=i_l;i<i_r;i++){if(inorder[i]==preorder[p_l]) break;count++;}root->left=buildTree_(preorder,p_l+1,p_l+count+1,inorder,i_l,i_l+count);root->right=buildTree_(preorder,p_l+count+1,p_r,inorder,i_l+1+count,i_r);return root;}
};