106. Construct Binary Tree from Inorder and Postorder Traversal (Medium)

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

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

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

For example, given

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

Return the following binary tree:

    3
   / \
  9  20
    /  \
   15   7

Solutions

class Solution {

    // Keep the index for specific node in inorder sequence which boosts up the efficiency
    // of searching for split point.
    Map<Integer, Integer> inorderMap = new HashMap<>();

    public TreeNode buildTree(int[] inorder, int[] postorder) {
        if (inorder == null || postorder == null || inorder.length != postorder.length) {
            return null;
        }

        for (int i = 0; i < inorder.length; i++) {
            inorderMap.put(inorder[i], i);
        }

        return recurse(inorder, 0, inorder.length - 1, postorder, 0, inorder.length - 1);
    }

    private TreeNode recurse(int[] inorder, int startIn, int endIn, int[] postorder, int startPost, int endPost) {
        if (startIn > endIn || startPost > endPost) {
            return null;
        }

        // Take in following example when working on boundary problems.

        // in order [9, x, 15, 20, 7]
        // post order [9, 15, 7, 20, x]

        // the last output node in post-order sequence is the root
        int val = postorder[endPost];

        TreeNode root = new TreeNode(val);

        // midIn = 1
        int midIn = inorderMap.get(val);

        // midIn - startIn represents the length of left tree
        // midPost = 0+1-0=1
        int midPost = startPost + midIn - startIn;

        // 1. For in-order output, [startIn:midIn-1] are left nodes, [midIn+1:endIn] are right nodes.
        // 2. For post-order output, [startPost:midPost] are left nodes, [midPost+1:endPost - 1] are the right nodes

        // in order [0,0], post order [0,0]
        root.left = recurse(inorder, startIn, midIn - 1, postorder, startPost, midPost - 1);

        // in order [2,4], post order [1, 3]
        root.right = recurse(inorder, midIn + 1, endIn, postorder, midPost, endPost - 1);

        return root;
    }
}

Incorrect Solutions

References

Copyright © iovi.com 2017 all right reserved,powered by GitbookLast Modification: 2019-12-03 11:01:18

results matching ""

    No results matching ""