Java - Top down recursion - python style slicing


  • 0
    D

    Another solution also referenced a useful resource. http://articles.leetcode.com/construct-binary-tree-from-inorder-and-preorder-postorder-traversal

    I use one helper method that simply acts as (List<Integer>).indexOf(val).

    The idea is simple:

    1. Preorder traversal always visits the root first.
    2. That node marks the center of the remainder of the node in the inorder array. That is everything to the left of the val will be in the left subtree, and everything to the right will be in the right subtree.

    One key insight to realize is that inorder traversal is a dfs traversal, visiting LEFT nodes after the root, before visiting RIGHT nodes. This means that all the nodes, say k nodes to the left of the inorder center, will appear in some order (we dont know the order yet!) as the next k nodes to the right of recently popped leftest element in the preorder.

    public TreeNode buildTree(int[] preorder, int[] inorder) {
            if (preorder == null || preorder.length == 0) {
                return null;            
            }
            
            int rootVal = preorder[0];
            TreeNode root = new TreeNode(rootVal);
            int slice = indexOf(inorder, rootVal);
            
            // on slicing the preorder arrays, we shift by 1. We have already consumed the first value
            int[] leftPreorder = Arrays.copyOfRange(preorder, 1, slice + 1);
            int[] rightPreorder = Arrays.copyOfRange(preorder, slice + 1, preorder.length);
            
            // on slicing the inorder array, we discard inorder[slice], already consumed.
            int[] leftInorder = Arrays.copyOfRange(inorder, 0, slice);
            int[] rightInorder = Arrays.copyOfRange(inorder, slice + 1, inorder.length);
            
            root.left = buildTree(leftPreorder, leftInorder); 
            root.right = buildTree(rightPreorder, rightInorder);
            
            return root;
        }
        
        
        public int indexOf(int[] arr, int val) {
            for (int index = 0; index < arr.length; index++) {
                if (arr[index] == val) {
                    return index;
                }
            }
            return -1;
        }
    

Log in to reply
 

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