[LeetCode-20]Construct Binary Tree from Inorder and Postorder Traversal

Given inorder and postorder traversal of a tree, construct the binary tree.

Note:

You may assume that duplicates do not exist in the tree.

the idea is similar with the former one [Leetcode-21]

java

public TreeNode buildTree(int[] inorder, int[] postorder) {

		return buildIP(inorder, postorder, 0, inorder.length-1, 0, postorder.length-1);

    }

	public TreeNode buildIP(int[] inorder, int[] postorder, int i_s, int i_e, int p_s, int p_e){

		if(p_s>p_e)

			return null;

		int pivot = postorder[p_e];

		int i = i_s;

		for(;i<=i_e;i++){

			if(inorder[i]==pivot)

				break;

		}

		TreeNode node = new TreeNode(pivot);

		int lenRight = i_e-i;

		node.left = buildIP(inorder, postorder, i_s, i-1, p_s, p_e-lenRight-1);

		node.right = buildIP(inorder, postorder, i+1, i_e, p_e-lenRight, p_e-1);

		return node;

	}

c++

TreeNode *BuildTreeIP(

        vector<int> &inorder,

        vector<int> &postorder,

        int i_s, int i_e,

        int p_s, int p_e){

        if(i_s > i_e) return NULL;

        int pivot = postorder[p_e];

        int i = i_s;

        for(;i<i_e;i++){

            if(inorder[i] == pivot)

                break;

        }

        int length1 = i-i_s;

        int length2 = i_e-i;

        TreeNode *node = new TreeNode(pivot);

        node->left = BuildTreeIP(inorder, postorder, i_s, i-1, p_s, p_s+length1-1);

        node->right = BuildTreeIP(inorder, postorder, i+1, i_e, p_e-length2, p_e-1);

        return node;

    }

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

        return BuildTreeIP(inorder, postorder, 0, inorder.size()-1, 0, postorder.size()-1);

    }