1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44
| public class Solution105Case1 {
private Map<Integer, Integer> indexMap; public TreeNode myBuildTree(int[] preorder, int[] inorder, int preorder_left, int preorder_right, int inorder_left, int inorder_right) { if (preorder_left > preorder_right) { return null; }
int preorder_root = preorder_left; int inorder_root = indexMap.get(preorder[preorder_root]);
TreeNode root = new TreeNode(preorder[preorder_root]); int size_left_subtree = inorder_root - inorder_left; root.left = myBuildTree(preorder, inorder, preorder_left + 1, preorder_left + size_left_subtree, inorder_left, inorder_root - 1); root.right = myBuildTree(preorder, inorder, preorder_left + size_left_subtree + 1, preorder_right, inorder_root + 1, inorder_right); return root; }
public TreeNode buildTree(int[] preorder, int[] inorder) { int n = preorder.length; indexMap = new HashMap<Integer, Integer>(); for (int i = 0; i < n; i++) { indexMap.put(inorder[i], i); } return myBuildTree(preorder, inorder, 0, n - 1, 0, n - 1); }
public static void main(String[] args) { int[] preorder = {3, 9, 20, 15, 7}; int[] inorder = {9, 3, 15, 20, 7}; Solution105Case1 solution = new Solution105Case1(); TreeNode treeNode = solution.buildTree(preorder, inorder); System.out.println(treeNode); } }
|