105. Construct Binary Tree from Preorder and Inorder Traversal (Medium)

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

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

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

For example, given

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

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[] preorder, int[] inorder) {
        if (preorder == null || inorder == null || preorder.length != inorder.length) {
            return null;
        }

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

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

    private TreeNode recurse(int[] preorder, int startPre, int endPre, int[] inorder, int startIn, int endIn) {
        if (startPre > endPre || startIn > endIn) {
            return null;
        }

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

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

        // the first output node in post-order sequence is the root
        int val = preorder[startPre];

        TreeNode root = new TreeNode(val);

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

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

        // 1. For pre-order output, [startPre+1:midPre] are left nodes, [midPre+1:endPre] are the right nodes
        // 2. For in-order output, [startIn+0:midIn-1] are left nodes, [midIn+1:endIn] are right nodes.

        // pre order [1,1], inorder [0,0]
        root.left = recurse(preorder, startPre + 1, midPre, inorder, startIn, midIn - 1);

        // pre order [2,4], in order [2,4]
        root.right = recurse(preorder, midPre + 1, endPre, inorder, midIn + 1, endIn);

        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 ""