Construct Binary Tree from Inorder and Postorder Traversal (Java)

LeetCode

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

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

	//2/4/2014 rewrite code
	public class Solution {
	public TreeNode buildTree(int[] inorder, int[] postorder) {
	if (inorder==null||inorder.length==0||postorder==null ||postorder.length==0){
	return null;
	}
	int iSt=0;
	int iEd=inorder.length-1;
	int pSt=0;
	int pEd=postorder.length-1;
	return buildTree(inorder, iSt, iEd, postorder, pSt, pEd);
	}
	private TreeNode buildTree(int[] inorder, int iSt, int iEd, int[] postorder, int pSt, int pEd){
	if (iSt>iEd || pSt>pEd){
	return null;
	}
	TreeNode root=new TreeNode (postorder[pEd]);
	int index=0;
	for (int i=iSt; i<=iEd; i++){
	if (inorder[i]==root.val){
	index=i;
	break;
	}
	}
	int len=index-iSt;
	root.left=buildTree(inorder, iSt, index-1, postorder, pSt, pSt+len-1);
	root.right=buildTree(inorder, index+1, iEd, postorder, pSt+len-1+1, pEd-1);
	return root;
	}
	}
	/**
	* Definition for binary tree
	* public class TreeNode {
	* int val;
	* TreeNode left;
	* TreeNode right;
	* TreeNode(int x) { val = x; }
	* }
	*/
	public class Solution {
	public TreeNode buildTree(int[] inorder, int[] postorder) {
	// Start typing your Java solution below
	// DO NOT write main() function
	int inorder_start=0;
	int inorder_end=inorder.length-1;
	int postorder_start=0;
	int postorder_end=postorder.length-1;
	return buildTree(inorder, inorder_start, inorder_end,
	postorder, postorder_start, postorder_end
	);
	}
	public TreeNode buildTree(int[] inorder, int inorder_start, int inorder_end,int[] postorder, int postorder_start, int postorder_end)
	{
	if (inorder_start>inorder_end||postorder_start>postorder_end){
	return null;
	}
	int rootVal=postorder[postorder_end];
	TreeNode root= new TreeNode(rootVal);
	for (int i=inorder_start; i<=inorder_end; i++){
	if (inorder[i]==rootVal){
	TreeNode left=buildTree(inorder, inorder_start, i-1,
	postorder, postorder_start,
	postorder_start+i-inorder_start-1);"Memoried the boundary case"
	TreeNode right=buildTree(inorder, i+1, inorder_end,
	postorder, postorder_end-inorder_end+i,postorder_end-1);"memoried the boundary case"
	root.left=left;
	root.right=right;
	}
	}
	return root;
	}
	}

view raw ConstructBinaryTreeFromInorderArrayAndPostorderArray.java hosted with ❤ by GitHub