Simple Java solution


  • 0
    L
        public TreeNode buildTree(int[] preorder, int[] inorder)
      {
        if (preorder.length != inorder.length || preorder.length == 0)
        {
          return null;
        }
        List<Integer> pre =
            Arrays.stream(preorder).boxed().collect(Collectors.toList());
        final HashMap<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < inorder.length; i++)
        {
          map.put(inorder[i], i);
        }
        List<Integer> in =
            Arrays.stream(inorder).boxed().collect(Collectors.toList());
        return helper(pre, 0, pre.size() - 1, in, 0, in.size() - 1, map);
      }
    
    
    
      private TreeNode helper(List<Integer> pre, int preStart, int preEnd,
          List<Integer> in, int inStart, int inEnd,
          HashMap<Integer, Integer> map)
      {
        if (preStart > preEnd || inStart > inEnd)
        {
          return null;
        }
        int indexofRoot = map.get(pre.get(preStart));// can't be null.
        int leftSize = indexofRoot - inStart;
        TreeNode root = new TreeNode(pre.get(preStart));
        root.left = helper(pre, preStart + 1, preStart + leftSize, in,
            inStart, indexofRoot - 1, map);
        root.right = helper(pre, preStart + 1 + leftSize, preEnd, in,
            indexofRoot + 1, inEnd, map);
        return root;
      }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.