leetcode: Construct Binary Tree from Inorder and Postorder Traversal

时间:2023-01-06 12:25:34
/**
 * 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() != postorder.size())
            return NULL;
        return core( inorder, 0, inorder.size()-1, postorder, 0, postorder.size()-1);
    }
    TreeNode *core( vector< int> &inorder, int left, int right, vector< int> &postorder, int start, int end){
        if( left > right || start > end)
            return NULL;
        TreeNode *root = new TreeNode( postorder[end]);
        int i = left;
        for( ; i <= right; ++i){
            if( inorder[i] == postorder[end])
                break;
        }
        root->left = core( inorder, left, i-1, postorder, start, start+(i-left)-1);//这里要用下标减left,算offset。不然会数组越界
        root->right = core( inorder, i+1, right, postorder, start+(i-left), end-1);//这里要用下标减left。算offset,不然会数组越界
        return root;
    }
};