Leetcode: Construct Binary Tree from Inorder and Postorder Traversal

/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
private:
    TreeNode *makeNode(vector<int>::iterator inBegin, vector<int>::iterator inEnd, vector<int>::iterator postBegin, vector<int>::iterator postEnd)
    {
        if (postBegin == postEnd) return nullptr;
        //从中序遍历结果中找出根节点（根节点在后序遍历中是最后一个节点）
        vector<int>::iterator itRoot = find(inBegin, inEnd, *(postEnd - 1));
        TreeNode *root = new TreeNode(*itRoot);
        //计算根的左子树节点个数
        int leftSize = itRoot - inBegin;
        //在中序遍历结果中根节点的左边是左子树中序遍历结果，右边是右子树中序遍历结果
        //在后序遍历结果中除去根节点前leftSize个节点是左子树前序遍历结果，后面的节点是右子树前序遍历结果
        root->left = makeNode(inBegin, itRoot, postBegin, postBegin + leftSize);
        root->right = makeNode(itRoot + 1, inEnd, postBegin + leftSize, postEnd - 1);
        return root;
    }

public:
    TreeNode *buildTree(vector<int> &inorder, vector<int> &postorder)
    {
        if (postorder.empty()) return nullptr;
        TreeNode *root = makeNode(inorder.begin(), inorder.end(), postorder.begin(), postorder.end());
        return root;
    }
};

/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    private TreeNode makeNode(int[] inorder, int inBegin, int inEnd, int[] postorder, int postBegin, int postEnd) {
        if (postBegin == postEnd) return null;
        int index = 0;
        for (int i = inBegin; i < inEnd; i++) {
            if (inorder[i] == postorder[postEnd - 1]) {
                index = i;
            }
        }
        int leftSize = index - inBegin;
        TreeNode root = new TreeNode(postorder[postEnd - 1]);
        root.left = makeNode(inorder, inBegin, inBegin + leftSize, postorder, postBegin, postBegin + leftSize);
        root.right = makeNode(inorder, index + 1, inEnd, postorder, postBegin + leftSize, postEnd - 1);
        return root;
    }

    public TreeNode buildTree(int[] inorder, int[] postorder) {
        if (postorder.length == 0) return null;
        TreeNode root = makeNode(inorder, 0, inorder.length, postorder, 0, postorder.length);
        return root;
    }
}