Construct Binary Tree from Preorder and Inorder Traversal
My Java solution to LeetCode problem #105:
Given preorder and inorder traversal of a tree, construct the binary tree. You may assume that duplicates do not exist in the tree.
public class Solution { private TreeNode buildTree(final int[] inorder, final int inStart, final int inEnd, final int[] preorder, final int preStart) { // Reached a null leaf if (inStart == inEnd || preStart >= preorder.length) { return null; } final TreeNode root = new TreeNode(preorder[preStart]); // Find the location of the root in inorder. Going backwards is faster, likely // due to particular test cases where root is found faster this way. int rootInorderPos; for (rootInorderPos = inEnd - 1; rootInorderPos >= inStart; rootInorderPos--) { if (inorder[rootInorderPos] == root.val) { break; } } root.left = this.buildTree(inorder, inStart, rootInorderPos, preorder, preStart + 1); final int leftSubtreeSize = rootInorderPos - inStart; root.right = this.buildTree(inorder, rootInorderPos + 1, inEnd, preorder, preStart + leftSubtreeSize + 1); return root; } public TreeNode buildTree(int[] preorder, int[] inorder) { return this.buildTree(inorder, 0, inorder.length, preorder, 0); } }