Java - Not very efficient but definitely easy to understand


  • 1
    T

    A good starting point if you are struggling with this question.

    As we know, the first element of preorder sequence is going to be the root of the tree. Find this element in the inorder array. Once index found, all the elements to the left of this in the inorder will form the left subtree and on the right will form the right subtree.

    During the next recursion call pass either the left subtree first or right (doesn't matter) but make sure you pass the right subset of the array as inStart and inEnd .

    For example, if you recurse with the left subtree (as in code below) make sure you pass inStart = inStart and inEnd = index-1 . index here is the index of the next preorder element in the inorder array.

    Next, when you recurse with the right subtree make sure you pass the inStart = index+1 while inEnd remains the same.

    Hope it helps. Let me know in case any questions.

    /**
     * Definition for a binary tree node.
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode(int x) { val = x; }
     * }
     */
    public class Solution {
        int preStart = 0;
        public TreeNode buildTree(int[] preorder, int[] inorder) {
            int n = preorder.length;
            if(n==0) return null;
            
            return helper(preorder, inorder, 0, n-1);
        }
        
        private TreeNode helper(int[] preorder, int[] inorder, int inStart, int inEnd){
            if(inEnd<inStart || preStart>=preorder.length) return null;
            
            TreeNode root = new TreeNode(preorder[preStart++]);
            
            int index=-1;
            for(int i = inStart;i<=inEnd;i++){
                if(inorder[i] == root.val){
                    index = i;
                    break;
                }
            }
            root.left = index==-1 ? null : helper(preorder, inorder, inStart,index-1);
            root.right = index==-1 ? null : helper(preorder,inorder, index+1, inEnd);
            
            return root;
        }
    }
    

Log in to reply
 

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