106. Construct Binary Tree from Inorder and Postorder Traversal

二刷
Version #2 Iterative

感觉特别特别难, 希望下次做能更理解
91.24 % 
class Solution {
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        if (inorder == null || inorder.length == 0
            || postorder == null || postorder.length == 0
            || inorder.length != postorder.length) return null;
        int inPointer = inorder.length - 1;
        int postPointer = postorder.length - 1;
        //                inp
        // inorder = [9,3,15,20,7]
        //             postp
        // postorder = [9,15,7,20,3]
        Stack<TreeNode> stack = new Stack<>();
        TreeNode root = new TreeNode(postorder[postPointer]);
        stack.push(root);
        postPointer--;
        TreeNode prev = null;
        TreeNode curr = null;
        while (postPointer >= 0) {
            while (!stack.isEmpty() && stack.peek().val == inorder[inPointer]) {
                prev = stack.pop();
                inPointer--;
            }
            // Walk down to the right most node
            curr = new TreeNode(postorder[postPointer--]);
         
            if(prev == null) { // stack won't be null if prev == null
                stack.peek().right = curr;
            } else {
                prev.left = curr;
             
            }
            prev = null;
            stack.push(curr);
        }
        return root;
    }
}



Version #1
Divide and conquer + HashMap Cache
Time O(n)
Space O(n)
 91.21 %
class Solution {
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        if (inorder == null || postorder == null || inorder.length != postorder.length) throw new IllegalArgumentException();
        Map<Integer, Integer> inMap = new HashMap<>();
        for (int i = 0; i < inorder.length; i++) {
            inMap.put(inorder[i], i);
        }
        return buildTreeHelper(inorder, postorder, 0, inorder.length - 1, 0, postorder.length - 1, inMap);
     
    }
    private TreeNode buildTreeHelper(int[] inorder, int[] postorder,
                                     int inStart, int inEnd, int postStart, int postEnd,
                                     Map<Integer, Integer> inMap) {
        if (inStart > inEnd || postStart > postEnd) {
            return null;
        }
        int curr = postorder[postEnd];
        TreeNode currNode = new TreeNode(curr);
        if (inStart != inEnd) {
            int i = inMap.get(curr);
            currNode.left = buildTreeHelper(inorder, postorder, inStart, i - 1, postStart, postStart + (i - 1 - inStart), inMap);
            currNode.right = buildTreeHelper(inorder, postorder, i + 1, inEnd, postEnd - inEnd + i, postEnd - 1, inMap);
            // inEnd - i - 1 = postEnd - 1 - x
        }
     
        return currNode;
    }
}

Version #2
Iterative

一刷
和105是一样的题
注意PostOrder是
 LEFT -> RIGHT -> ROOT
28.94 %
public class Solution {
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        if (inorder == null || postorder == null) return null;
        //TODO
        return buildTree(inorder, 0, inorder.length - 1, postorder, postorder.length - 1);
    }
    private TreeNode buildTree(int[] inorder, int inStart, int inEnd, int[] postorder, int postEnd) {
        if (inStart > inEnd || inEnd >= inorder.length) return null;
        int rootVal = postorder[postEnd];
        int inIndex = 0;
        for (int i = inStart; i <= inEnd; i++) {
            if (inorder[i] == rootVal) inIndex = i;
        }
        int rightLength = inEnd - inIndex;
        TreeNode root = new TreeNode(rootVal);
        root.right = buildTree(inorder, inIndex + 1, inEnd, postorder, postEnd - 1);
        root.left = buildTree(inorder, inStart, inIndex - 1, postorder, postEnd - 1 - rightLength);
        return root;
    }
}