106. Construct Binary Tree from Inorder and Postorder Traversal.md

Difficulty	Related Topics	Similar Questions
Medium	Array Tree Depth-first Search https://leetcode.com/tag/array https://leetcode.com/tag/tree https://leetcode.com/tag/depth-first-search	Construct Binary Tree from Preorder and Inorder Traversal https://leetcode.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal

106. Construct Binary Tree from Inorder and Postorder Traversal

Problem:

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

Solution:

Pattern of inorder traversal result: in(root) = in(root.left) + root + in(root.right)

Pattern of postorder traversal result: post(root) = post(root.left) + post(root.right) + root

There are no duplicates so get the first item in preorder result, pinpoint it in inorder result. Then we know the size of left and right subtree.

Repeat the process on subtrees.

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

function _buildTree (postorder, inorder, pStart, pEnd, iStart, iEnd) {
  if (pStart >= pEnd || iStart >= iEnd) {
    return null
  }
  const val = postorder[pEnd - 1]
  const node = new TreeNode(val)
  for (let i = iStart; i < iEnd; i++) {
    if (val === inorder[i]) {
      node.left = _buildTree(postorder, inorder, pStart, i - iStart + pStart, iStart, i)
      node.right = _buildTree(postorder, inorder, (i + 1) - iEnd + (pEnd - 1), pEnd - 1, i + 1, iEnd)
      break
    }
  }
  return node
}

Template generated via Leetmark.