20ms java easy to understand recursive solution


  • 2
    Z
    /**
     * Definition for a binary tree node.
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode(int x) { val = x; }
     * }
     */
    public class Solution {
        public TreeNode buildTree(int[] inorder, int[] postorder) {
            if (postorder.length == 0||inorder.length==0) return null;
            TreeNode root = helper(inorder, postorder, postorder.length-1, 0,postorder.length-1 );
            return root;
    
        }
        
        private TreeNode helper(int[] inorder, int[] postorder,int rootIdx, int start, int end){
            if (start > end||start<0||end>=inorder.length) return null;
            TreeNode root = new TreeNode(postorder[rootIdx]);
            int index = findIdx(inorder,start,end, root.val);
            int leftSize = end-index ;
            root.left = helper(inorder,postorder,rootIdx-1-leftSize,start,index-1);
            root.right = helper(inorder,postorder,rootIdx-1,index+1,end);
            return root;
        }
        
        private int findIdx(int[] inorder, int start, int end, int key) {
            for (int i = start; i <= end; i++) {
                if (inorder[i] == key) return i;
            }
            return -1;
        }    
    }

  • 0
    T

    Could any one please explain why leftSize = end-index ? not rightSize?


  • 0
    Z

    Hi TenffY, you are right, it's a typo because it's quite similar to the solution of preorder, so I forgot to change the var name. Sorry for the confusion.


Log in to reply
 

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