博客

通过中序和后序建立一个二叉树（或前序和中序），递归解法三点要注意的：

1.不要new新的vector来存储左子树和右子树的中序和后序序列，这样做容易


Memory Limit Exceeded

2.构造新函数的时候参数值要记得用引用，要不然也会


Memory Limit Exceeded

3.弄清楚左子树（右子树）的中序（后序）的起始点和终止点的下标

/**
 * Definition for binary tree
 * 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() == 0 || postorder.size() == 0 || inorder.size() != postorder.size()){
            return NULL;
        }
        
        return buildTree(inorder, 0, inorder.size() - 1, postorder, 0, postorder.size() - 1);
    }
    
    TreeNode *buildTree(vector<int> &inorder, int in_start, int in_end, vector<int> &postorder, int post_start, int post_end){
        if(in_start > in_end || post_start > post_end)
            return NULL;
            
        int i, j;
        int val = postorder.at(post_end);
        TreeNode *root = new TreeNode(val);
        for(i = in_start; i <= in_end; i++){
            if(inorder.at(i) == val)
                break;
        }
        
        TreeNode *left = buildTree(inorder, in_start, i - 1, postorder, post_start, post_start + i - in_start - 1);
        TreeNode *right = buildTree(inorder, i + 1, in_end, postorder, post_start + i - in_start, post_end - 1);
        root -> left = left;
        root -> right = right;
        return root;
    }
};