106-construct-binary-tree-from-inorder-and-postorder-traversal

Question

https://leetcode.com/problems/construct-binary-tree-from-inorder-and-postorder-traversal/description/

Given inorder and postorder traversal of a tree, construct the binary tree.

Note:

You may assume that duplicates do not exist in the tree.

Example:

inorder = [9,3,15,20,7]
postorder = [9,15,7,20,3]

Return the following binary tree:
    3
   / \
  9  20
    /  \
   15   7

Thought Process

1. Inorder travels by the order of left, parent, right
2. Postorder travels by left, right, parent
3. This is similar to105-Construct Binary Tree from Preorder and Inorder Traversal , unlike preorder where the root is at the front, postorder's root is at the end
4. Time complexity O(n)
5. Space complexity O(n)

Solution

class Solution {
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        if (inorder == null || inorder.length != postorder.length) return null;
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < inorder.length; i++) {
            map.put(inorder[i], i);
        }
        return build(inorder, 0, inorder.length - 1, postorder, postorder.length - 1, map);
    }

    private TreeNode build(int[] inorder, int iLo, int iHi, int[] postorder, int pHi, Map<Integer, Integer> map) {
        if (iLo > iHi) return null;
        if (iLo == iHi) return new TreeNode(inorder[iLo]);
        TreeNode root = new TreeNode(postorder[pHi]);
        int id = map.get(root.val);
        root.left = build(inorder, iLo, id - 1, postorder, pHi - (iHi - id) - 1, map);
        root.right = build(inorder, id + 1, iHi, postorder, pHi - 1, map);
        return root;
    }
}

class Solution {
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        if (inorder == null || inorder.length == 0 || inorder.length != postorder.length) return null;
        Stack<TreeNode> stack = new Stack<>();
        int iId = inorder.length - 1, pId = iId;
        TreeNode root = new TreeNode(postorder[pId--]);
        TreeNode pre = null;
        stack.push(root);
        // because the last element is the root, and the element before the the root 
        // of its right subtree
        while (pId >= 0) {
            while (!stack.isEmpty() && stack.peek().val == inorder[iId]) {
                iId--;
                pre = stack.pop();
            }
            TreeNode node = new TreeNode(postorder[pId--]);
            if (pre != null) pre.left = node;
            else if (!stack.isEmpty()) stack.peek().right = node;
            stack.push(node);
            pre = null;
        }
        return root;
    }
}

class Solution {
    int iId, pId;
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        if (inorder == null || inorder.length == 0 || inorder.length != postorder.length) return null;
        iId = inorder.length - 1;
        pId = iId;
        return build(inorder, postorder, null);
    }

    private TreeNode build(int[] inorder, int[] postorder, TreeNode pre) {
        if (pId < 0) return null;
        TreeNode root = new TreeNode(postorder[pId--]);
        if (root.val != inorder[iId]) root.right = build(inorder, postorder, root);
        iId--;
        if (pre == null || pre.val != inorder[iId]) root.left = build(inorder, postorder, pre);
        return root;
    }
}

Additional