Construct Binary Tree from Inorder and Postorder Traversal

Analysis:
Mirror problem of Construct Binary Tree from Inorder and Preorder Traversal. Reverse of postorder is root -> right ->left. So start from the end of the postorder array. Have to be extremely careful when dealing with left and right of inorder array.
Solution:

 /**  
  * Definition for a binary tree node.  
  * public class TreeNode {  
  *   int val;  
  *   TreeNode left;  
  *   TreeNode right;  
  *   TreeNode(int x) { val = x; }  
  * }  
  */  
 class Solution {  
   public TreeNode buildTree(int[] inorder, int[] postorder) {  
     Map<Integer, Integer> inMap = new HashMap<>();  
           for (int i = 0; i < inorder.length; i++) {  
                inMap.put(inorder[i], i);  
           }  
           return helper(postorder.length - 1, 0, inorder.length - 1, postorder, inMap);  
   }  
      private TreeNode helper(int postStart, int inStart, int inEnd, int[] postorder, Map<Integer, Integer> inMap) {  
           if (inStart > inEnd) return null;  
           TreeNode root = new TreeNode(postorder[postStart]);  
     int inIndex = inMap.get(root.val);  
           root.right = helper(postStart - 1, inIndex + 1, inEnd, postorder, inMap);  
           root.left = helper(postStart - (inEnd - inIndex + 1), inStart, inIndex - 1, postorder, inMap);  
           return root;  
      }  
 }  

评论

此博客中的热门博文

663. Equal Tree Partition

776. Split BST

426. Convert Binary Search Tree to Sored Doubly Linked List