Javascript solution with explanation


  • 0
    L
    • Since there dulplicate items, we can split any order into two parts(one could be null), we can build tree from preorder by spliting inorder with the first element of preorder

    • Step1: Spllit inorder into part1 and part2 using preorder[0](and pop preorder[0] as the root element)

    • Step2: If part1 is not null,split part1 into part1-1 and part1-2 using preorder[0](pop preorder[0] as the left of which parted out part1)

    • Repeat Step2

    • Step3: If part 2 is not null split part2 into part2-1 and part2-2 using preorder[0](pop preorder[0] as the right of which parted out part2)

    • Repeat till preorder is null

    var buildTree = function(preorder,inorder) {
        if(!preorder.length)
            return null;
    
        var t=new TreeNode(preorder.splice(0,1)[0]);
    
        function build(part,parent){
            if(!preorder.length)
                return;
    
            var left = part.slice(0,part.indexOf(parent.val));
            var right = part.slice(1+part.indexOf(parent.val),part.length);
    
            if(left.length){
                var pl=new TreeNode(preorder.splice(0,1)[0]);
                parent.left = pl;
                build(left,pl);
            }
    
            if(right.length){
                var pr=new TreeNode(preorder.splice(0,1)[0]);
                parent.right = pr;
                build(right,pr);
            }
        }
    
        build(inorder,t);
    
        return t;
    };
    

Log in to reply
 

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