LeetCode-Construct Binary Tree From Inorder and Postorder Traversal

https://leetcode-cn.com/problems/construct-binary-tree-from-inorder-and-postorder-traversal/

和上一题Construct Binary Tree from Preorder and Inorder Traversal思路几乎一模一样，在此不多赘述。

/**
 * 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* build(vector<int>& inorder, vector<int>& postorder, int in_l, int in_r, int post_l, int post_r) {
        if(in_l>in_r || post_l>post_r) return nullptr;
        int root_val = postorder[post_r];
        TreeNode* root = new TreeNode(root_val);
        int in_split_pos = in_r;
        for(int i=in_r; i>=in_l; --i) {
            if(inorder[i] == root_val) {
                in_split_pos = i;
                break;
            }
        }
        int diff = in_r - in_split_pos;
        root->right = build(inorder, postorder, in_split_pos+1, in_r, post_r-diff, post_r-1);
        root->left = build(inorder, postorder, in_l, in_split_pos-1, post_l, post_r-diff-1);
        return root;
    }
    TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
        int len = inorder.size();
        if(len==0) return nullptr;
        return build(inorder, postorder, 0, len-1, 0, len-1);
    }
};