1. 106

construct-binary-tree-from-inorder-and-postorder-traversal

2. 算法

• O(n)

3. 代码

struct TreeNode {

      int val;

      TreeNode *left;

      TreeNode *right;

      TreeNode(int x) : val(x), left(NULL), right(NULL) {}

  };

// ps是preoreder的第一个元素下标，is是inoreder的第一个元素的下标

class Solution {

private:

    TreeNode *dfs(vector<int> &inorder,vector<int> &postorder,int is,int ps,int len){

        if(len<=0)

            return NULL;

        TreeNode *root=new TreeNode(postorder[ps]);

        for(int i=0;i<len;i++){

            if(inorder[is-i ]==root->val){

                root->right=dfs(inorder,postorder,is,ps-1,i );

                root->left=dfs(inorder,postorder,is-i-1,ps-i-1,len-i-1);

                break;

            }

        }

        return root;

    }

public:

    TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {

        return dfs(inorder,postorder,inorder.size()-1,postorder.size()-1,inorder.size());

    }

};