Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- //Recursive solution
- //Time: O(n), 3ms
- //Space: O(h)
- class Solution {
- public TreeNode buildTree(int[] inorder, int[] postorder) {
- //Hash all the value in a HashTable so that we can look up the index in the inorder of a value in O(1) time
- Map<Integer, Integer> map = new HashMap<>();
- for(int i = 0; i < inorder.length; i++) {
- map.put(inorder[i], i);
- }
- return buildTreeR(inorder, postorder, 0, inorder.length, 0, postorder.length, map);
- }
- private TreeNode buildTreeR(int[] inorder, int[] postorder, int inBegin, int inEnd, int postBegin, int postEnd, Map<Integer, Integer> map) {
- if(inBegin == inEnd && postBegin == postEnd) return null;
- //The Last node of post-order is the root of the tree
- TreeNode root = new TreeNode(postorder[postEnd - 1]);
- int rootIndex = map.get(postorder[postEnd - 1]);
- //The left subtree and right subtree are divided by the root
- root.left = buildTreeR(inorder, postorder, inBegin, rootIndex, postBegin, postBegin + (rootIndex - inBegin), map);
- root.right = buildTreeR(inorder, postorder, rootIndex + 1, inEnd, postBegin + (rootIndex - inBegin), postEnd - 1, map);
- return root;
- }
- }
- /**
- * Definition for a binary tree node.
- * public class TreeNode {
- * int val;
- * TreeNode left;
- * TreeNode right;
- * TreeNode(int x) { val = x; }
- * }
- */
Add Comment
Please, Sign In to add comment