A concise, D&C, within 10 lines, JAVA solution. Any suggestions?


  • 0
    R

    The basic idea is divide and conquer, and at first I use Arrays.binarySearch() to locate the root index, however, it requies the array to be sorted first, which I cannot do in my program. So I write a arraySearch() methods myself.

    1. Find the root first. The root would be the last element of the postorder[].
    2. Find the index of root in inorder[].
    3. Divide the inorder[] and postorder[] into root.left part and root.right part.
    4. Repeat.

    I'm a newbee to JAVA, so despite the recursive approach, I think I'm using O(1) space and O(n) time in solving this problem. Am I right?

    And if there's any suggestions or advices you may have to my solution, I would be more than happy to take them all!!!

       /**
     * Definition for binary tree
     * 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(inorder==null||postorder==null||inorder.length==0||postorder.length==0||postorder.length!=inorder.length) return null;
            int rootVal = postorder[postorder.length-1];
            TreeNode root = new TreeNode(rootVal);
            int rootIndex = arraySearch(inorder, rootVal);
            if(rootIndex>0) root.left = buildTree(Arrays.copyOfRange(inorder, 0,rootIndex), Arrays.copyOfRange(postorder,0,rootIndex));
            if(rootIndex<inorder.length-1) root.right = buildTree(Arrays.copyOfRange(inorder, rootIndex+1,inorder.length),Arrays.copyOfRange(postorder,rootIndex,postorder.length-1));
            return root;
        }
        
        private int arraySearch(int[] A, int target){
            for(int i=0;i<A.length;i++){
                if(A[i]==target) return i;
            }
            return -1;
        }
    }

Log in to reply
 

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