**Problem:**

Given inorder and postorder 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[] inorder, postorder; int current; public TreeNode buildTree(int[] inorder, int[] postorder) { if (inorder == null || postorder == null || inorder.length != postorder.length) return null; this.inorder = inorder; this.postorder = postorder; current = postorder.length - 1; return buildTree(0, inorder.length - 1); } private int findIndex(int post) { for (int i = 0; i < inorder.length; i++) if (inorder[i] == postorder[post]) return i; return -1; } private TreeNode buildTree(int start, int end) { if (start > end) return null; TreeNode root = new TreeNode(postorder[current]); int index = findIndex(current); current--; root.right = buildTree(index + 1, end); root.left = buildTree(start, index - 1); return root; } }

Comments are closed.