2ms Java Solution


  • 2
    N
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        return buildTree(inorder,postorder,0,inorder.length-1,0,postorder.length-1);
    }
    
    private TreeNode buildTree(int[] inorder,int[] postorder,int instart,int inend, int poststart,int postend){
        if(instart>inend){
            return null;
        }
        int rootval = postorder[postend];
        TreeNode root = new TreeNode(rootval);
        int rootIndex = getRootIndex(inorder,rootval,instart,inend);
        root.left = buildTree(inorder,postorder,instart,rootIndex-1,poststart,poststart+(rootIndex-instart)-1);
        root.right = buildTree(inorder,postorder,rootIndex+1,inend,poststart+(rootIndex-instart),postend-1);
        return root;
    }
    
    private int getRootIndex(int[] inorder, int rootval, int p, int q){
        int i = p;int j = q;
         while(i<=j){
                if(inorder[i++]==rootval){
                    return --i;
                }
                if(inorder[j--]==rootval){
                    return ++j;
                }
           }
        return -1;
    }

Log in to reply
 

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