不具名的站点

问题

  根据一棵树的中序遍历与后序遍历构造二叉树。可以假设数中没有重复元素。例如，给出

中序遍历 inorder = [9,3,15,20,7]
后序遍历 postorder = [9,15,7,20,3]

返回以下二叉树

分析

  首先明确两点：
　　1. 后序遍历输出的数组，最后一个元素为树根。
　　2. 中序遍历输出的数组，树根左边的元素构成左子树，树根右边的元素构成右子树。
基于这两点，可以先从后序遍历中找到整个树的树根，再在中序遍历的结果中找到该树根，树根左边的元素即为左子树，右边的元素即为右子树。至此，该问题形成一个递归问题--左子树和右子树在后序遍历中也分别对应一个数组集合，对左子树和右子树分别递归即可还原原来的二叉树。

代码

/**
* 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* buildTree(vector<int>& inorder, vector<int>& postorder) {
　　　　if(inorder.size()!=postorder.size())
　　　　　　return NULL;
　　　　if(inorder.size()==0 || postorder.size()==0)
　　　　　　return NULL;

　　　　int length=inorder.size();
　　　　TreeNode* root=new TreeNode(postorder[length-1]);
　　　　int root_inorder_index=-1;
　　　　vector inorder_l,inorder_r,postorder_l,postorder_r;
　　　　for(int i=0;i<length;i++)
　　　　　　if(inorder[i]==postorder[length-1]){
　　　　　　　　root_inorder_index=i;
　　　　　　　　break;
　　　　　　}

　　　　for(int i=0;i<root_inorder_index;i++){
　　　　　　inorder_l.push_back(inorder[i]);
　　　　　　postorder_l.push_back(postorder[i]);
　　　　}

　　　　for(int i=root_inorder_index+1;i<inorder.size();i++){ 
　　　　　　inorder_r.push_back(inorder[i]); 
　　　　　　postorder_r.push_back(postorder[i-1]); 
　　　　} 

　　　　root->left=buildTree(inorder_l,postorder_l);
　　　　root->right=buildTree(inorder_r,postorder_r);
　　　　return root;
　　}
};