889. Construct Binary Tree from Preorder and Postorder Traversal

Version # 2 Iterative
Time O(n)
We keep walking down to the sub tree
Use stack to keep track of the path
When we see that current node's value in post[j], we know this subtree is done
We need to pop it out and construct other unfinished subtree which is on top of the stack

94.57 %
class Solution {
    public TreeNode constructFromPrePost(int[] pre, int[] post) {
        if (pre == null || post == null || pre.length != post.length || pre.length == 0) {
            return null;
        }

        Deque<TreeNode> stack = new ArrayDeque<>();
        stack.addFirst(new TreeNode(pre[0]));
        for (int i = 1, j = 0; i < pre.length; i++) {
           
            while (stack.peekFirst().val == post[j]) {
                stack.removeFirst();
                j++;
            }
            TreeNode curr = new TreeNode(pre[i]);
            if (stack.peekFirst().left == null) {
                stack.peekFirst().left = curr;
            } else {
                stack.peekFirst().right = curr;
            }
            stack.addFirst(curr);
        }
        return stack.removeLast();
    }
}



Version #1 Recursion without mem
Time O(nlogn)
Can be improved by using a hashmap to trace the values in post
94.57 %
class Solution {
    public TreeNode constructFromPrePost(int[] pre, int[] post) {
        if (pre == null || post == null || pre.length != post.length) {
            return null;
        }
        return build(pre, 0, pre.length - 1, post, 0, post.length - 1);
    }
 
    private TreeNode build(int[] pre, int preStart, int preEnd, int[] post, int postStart, int postEnd) {
        if (preStart > preEnd) {
            return null;
        }
        if (preStart == preEnd) {
            return new TreeNode(pre[preStart]);
        }
     
        TreeNode root = new TreeNode(pre[preStart]);
        preStart++;
        postEnd--;
        for (int i = postStart; i <= postEnd; i++) {
            if (pre[preStart] == post[i]) {
                root.left = build(pre, preStart, preStart + i - postStart, post, postStart, i);
                root.right = build(pre, preStart + i - postStart + 1, preEnd, post, i + 1, postEnd);
                break;
            }
        }
        return root;
    }
}