Construct Binary Tree from Preorder and Inorder Traversal (Java)

LeetCode

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

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

Solution: Divide and Conquer

According to the rule of preorder traversal,  the first item in the preorder array must be the root. and the question also told us "You may assume that duplicates do not exist in the tree." so we can go through inorder array find the root's position, then  we got left tree and right tree. finally we can apply recursion to got the tree we want base on above logic.

	/**
	* 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[] preorder, int[] inorder) {
	if (preorder==null||preorder.length==0|| inorder==null ||inorder.length==0){
	return null;
	}
	int pSt=0;
	int pEd=preorder.length-1;
	int iSt=0;
	int iEd=inorder.length-1;
	return buildTree(preorder, pSt, pEd, inorder, iSt, iEd);
	}
	private TreeNode buildTree(int[] preorder, int pSt, int pEd, int[] inorder, int iSt, int iEd){
	if (pSt>pEd || iSt>iEd){
	return null;
	}
	TreeNode root=new TreeNode (preorder[pSt]);
	int index=0;
	for (int i=iSt; i<=iEd; i++){
	if (inorder[i]==root.val){
	index=i;
	break;
	}
	}
	// length of left tree
	int len=index-iSt;
	// pay attention to bounds of preorder and inorder
	root.left=buildTree(preorder, pSt+1, pSt+1+len-1, inorder, iSt, index-1);
	root.right=buildTree(preorder, pSt+1+len-1+1, pEd, inorder, index+1, iEd);
	return root;
	}
	}

view raw ConstructBinaryTreeFromInorderArrayAndPreorderArray.java hosted with ❤ by GitHub