Straight forward Java recursion without helper, slow because of Arrays copy?


  • 0
    X
    /**
     * 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[] preorder, int[] inorder) {
            TreeNode root;
            if(preorder==null||preorder.length==0){
                return null;
            }
            
            int rootVal = preorder[0];
            int rootIdx = 0;
            
            root = new TreeNode(rootVal);
            
            for(int i=0;i<inorder.length;i++){
                if(inorder[i]==rootVal){
                    rootIdx = i;
                    break;
                }
            }
            int[] leftPreorder = null;
            int[] rightPreorder = null;
            
            int[] leftInorder = null;
            int[] rightInorder = null;
            
            if(rootIdx+1>1) leftPreorder = Arrays.copyOfRange(preorder,1,rootIdx+1);
            if(rootIdx+1<preorder.length) rightPreorder = Arrays.copyOfRange(preorder, rootIdx+1,preorder.length);
            
            if(rootIdx>0) leftInorder = Arrays.copyOfRange(inorder,0,rootIdx);
            if(rootIdx+1<inorder.length) rightInorder = Arrays.copyOfRange(inorder, rootIdx+1,inorder.length);
            
            
            root.left = buildTree(leftPreorder,leftInorder);
            root.right = buildTree(rightPreorder,rightInorder);
            return root;
        }
    }
    

Log in to reply
 

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