Guest User

Newsletter #187 Solution

a guest
Sep 12th, 2021
88
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. public class TreeNode {
  2.   int val;
  3.   TreeNode left;
  4.   TreeNode right;
  5.   TreeNode() {}
  6.    
  7.   TreeNode(int val) { this.val = val; }
  8.    
  9.   TreeNode(int val, TreeNode left, TreeNode right) {
  10.     this.val = val;
  11.     this.left = left;
  12.     this.right = right;
  13.   }
  14. }
  15.  
  16. class Solution {
  17.  
  18.   Map<Integer, Integer> inorderIdxMap;
  19.   int postorderIdx;
  20.   int[] postorder;
  21.  
  22.   public TreeNode buildTree(int[] inorder, int[] postorder) {
  23.     this.postorder = postorder;
  24.    
  25.     inorderIdxMap = new HashMap<Integer, Integer>();
  26.    
  27.     for (int i = 0; i < inorder.length; i++) {
  28.       inorderIdxMap.put(inorder[i], i);
  29.     }
  30.    
  31.     postorderIdx = postorder.length - 1;
  32.    
  33.     return buildTree(0, postorder.length - 1);
  34.   }
  35.  
  36.   private TreeNode buildTree(int inorderLeft, int inorderRight) {
  37.     if (inorderLeft > inorderRight) {
  38.       return null;
  39.     }
  40.    
  41.     int nodeValue = postorder[postorderIdx];
  42.     int rootIdx = inorderIdxMap.get(nodeValue);
  43.    
  44.     postorderIdx--;
  45.    
  46.     TreeNode node = new TreeNode(nodeValue);
  47.  
  48.     node.right = buildTree(rootIdx + 1, inorderRight);
  49.     node.left = buildTree(inorderLeft, rootIdx - 1);
  50.    
  51.     return node;
  52.   }
  53. }
RAW Paste Data