1ms Java Recursive Solution, beats 99.83%


  • 6
    S
    public TreeNode buildTree(int[] preorder, int[] inorder) {
            return buildTree(preorder, 0, inorder, inorder.length - 1, 0);
        }
        
        private TreeNode buildTree(int[] preorder, int idx, int[] inorder, int end, int start) {
            if (idx >= preorder.length || start > end) {
                return null;
            }
            TreeNode root = new TreeNode(preorder[idx]);
            int i;
            for (i = end; i >= start; i--) {
                if (preorder[idx] == inorder[i]) {
                    break;
                }
            }
            root.left = buildTree(preorder, idx + 1, inorder, i - 1, start);
            root.right = buildTree(preorder, idx + i - start + 1, inorder, end, i+1);
            return root;
        }

  • 0
    S

    your code doesn't pass the test [1,2][2,1]


  • 0

    @lsy1991121
    actually it works
    @scott-shao-5
    your idea is brilliant, though it may be confusing when calculating every idx things, but it is much faster

    UPDATE
    while i see it's because the testing set is unbalanced, and you start from the end, then it will be much faster LOL
    the complexity of our algorithm are just the same

    my solution use ps pe, is ie for preorder & inorder's start & end
    more readable but slower

        public TreeNode buildTree(int[] preorder, int[] inorder) {
            return helper(preorder, 0, preorder.length - 1, inorder, 0, inorder.length - 1);
        }
        
        public TreeNode helper(int[] preorder, int ps, int pe, int[] inorder, int is, int ie) {
            if (ps > pe || is > ie) {return null;}
            if (ps >= preorder.length) {return null;}
            TreeNode root = new TreeNode(preorder[ps]);
            int i = 0;
            while (inorder[i + is] != root.val) {i++;}
            root.left = helper(preorder, ps + 1, ps + i, inorder, is, is + i - 1);
            root.right = helper(preorder, ps + 1 + i, pe, inorder, is + i + 1, ie); 
            return root;
        }
    

  • 1
    B

    Actually, your code runs fast because you iterated the index 'i' decreasing from end to start, which is just catering the testing cases rather than real tricky.
    I changed it to " for (i = start; i <= end; i++) " and the time became 19 ms.


Log in to reply
 

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