Problem:
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:
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ public class Solution { int[] preorder, inorder; public TreeNode buildTree(int[] preorder, int[] inorder) { this.preorder = preorder; this.inorder = inorder; int n = preorder.length; return buildTree(0, n - 1, 0, n - 1); } private TreeNode buildTree(int pre1, int pre2, int in1, int in2) { if (pre2 < pre1) return null; if (pre2 == pre1) return new TreeNode(preorder[pre1]); TreeNode root = new TreeNode(preorder[pre1]); int pos = 0; for (int i = in1; i <= in2; i++) { if (inorder[i] == root.val) { pos = i; break; } } root.left = buildTree(pre1 + 1, pre1 + pos - in1, in1, pos - 1); root.right = buildTree(pre1 + pos - in1 + 1, pre2, pos + 1, in2); return root; } }