105. Construct Binary Tree from Preorder and Inorder Traversal

Difficulty:
Medium
Related Topics:
Similar Questions:

Problem

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

Solution (Java)

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    private int j;
    private Map<Integer, Integer> map = new HashMap<>();

    public int get(int key) {
        return map.get(key);
    }

    private TreeNode answer(int[] preorder, int[] inorder, int start, int end) {
        if (start > end || j > preorder.length) {
            return null;
        }
        int value = preorder[j++];
        int index = get(value);
        TreeNode node = new TreeNode(value);
        node.left = answer(preorder, inorder, start, index - 1);
        node.right = answer(preorder, inorder, index + 1, end);
        return node;
    }

    public TreeNode buildTree(int[] preorder, int[] inorder) {
        j = 0;
        for (int i = 0; i < preorder.length; i++) {
            map.put(inorder[i], i);
        }
        return answer(preorder, inorder, 0, preorder.length - 1);
    }
}

Solution (Javascript)

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {number[]} preorder
 * @param {number[]} inorder
 * @return {TreeNode}
 */
var buildTree = function(preorder, inorder) {
  return helper(preorder, inorder, 0, 0, inorder.length - 1);
};

var helper = function (preorder, inorder, preIndex, inStart, inEnd) {
  if (preIndex >= preorder.length || inStart > inEnd) return null;

  var index = 0;
  var root = new TreeNode(preorder[preIndex]);

  for (var i = inStart; i <= inEnd; i++) {
    if (inorder[i] === root.val) {
      index = i;
      break;
    }
  }

  if (index > inStart) root.left = helper(preorder, inorder, preIndex + 1, inStart, index - 1);
  if (index < inEnd) root.right = helper(preorder, inorder, preIndex + index - inStart + 1, index + 1, inEnd);

  return root;
};

Explain:

  1. preorder[0] 是 root
  2. 在 inorder 里找到 root，左边是 root.left，右边是 root.right。
  3. 递归

Complexity: