106. Construct Binary Tree from Inorder and Postorder Traversal

Description

Given two integer arrays inorder and postorder where inorder is the inorder traversal of a binary tree and postorder is the postorder traversal of the same tree, construct and return the binary tree.

Example 1:

Input: inorder = [9,3,15,20,7], postorder = [9,15,7,20,3]
Output: [3,9,20,null,null,15,7]

Example 2:

Input: inorder = [-1], postorder = [-1]
Output: [-1]

Constraints:

• 1 <= inorder.length <= 3000
• postorder.length == inorder.length
• 3000 <= inorder[i], postorder[i] <= 3000
• inorder and postorder consist of unique values.
• Each value of postorder also appears in inorder.
• inorder is guaranteed to be the inorder traversal of the tree.
• postorder is guaranteed to be the postorder traversal of the tree.

---

Solutions

Solution 1

Intuition

Code

class Solution {
    // inorder 9,3,15,20,7
    // postorder 9,15,7,20,3
    // 1. get 3 from postorder
    // 2. find 3 in inorder, and then split inorder to two parts
    // 3. recursion 1, 2 in different part
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        int m = inorder.length, n = postorder.length;
        if (m != n) {
            return null;
        }
        Stack<Integer> stack = new Stack<>();
        for (int val : postorder) {
            stack.push(val);
        }

        TreeNode root = helper(0, n - 1, stack, inorder);
        return root;
    }

    private TreeNode helper(
        int start, int end, Stack<Integer> stack, int[] inorder) {
        if (start > end || stack.isEmpty()) {
            return null;
        }
        TreeNode node = new TreeNode(stack.pop());

        // find root in inorder
        int index = start;
        for (int i = start; i <= end; i++) {
            if (inorder[i] == node.val) {
                index = i;
                                break;
            }
        }

        node.right = helper(index + 1, end, stack, inorder);
        node.left = helper(start, index - 1, stack, inorder);

        return node;
    }
}

Complexity

• Time: O(nlogn)
• Space: O(n)

---

Solution 2

Intuition

Code

Complexity

• Time:
• Space:

---

Similar Questions