从中序与后序遍历序列构造二叉树

[louzhedong]

习题

出处 LeetCode 算法第106题

根据一棵树的中序遍历与后序遍历构造二叉树。

注意:
你可以假设树中没有重复的元素。

例如，给出

中序遍历 inorder = [9,3,15,20,7]
后序遍历 postorder = [9,15,7,20,3]

返回如下的二叉树：

    3
   / \
  9  20
    /  \
   15   7

思路

通过观察，可以发现后序遍历的最后一个元素为root，找出这个元素在中序遍历中的位置，这个位置前的元素即为左子树的元素，这个元素后的元素为右子树的元素。通过递归，得出整个树

解答

function TreeNode(val) {
  this.val = val;
  this.left = this.right = null;
}

/**
 * @param {number[]} inorder
 * @param {number[]} postorder
 * @return {TreeNode}
 */
function helper(inorder, postorder) {
  if (inorder.length == 0 || postorder.length == 0) {
    return null;
  }
  var length = postorder.length;
  var rootVal = postorder[length - 1];
  var index = inorder.indexOf(rootVal);
  var inorderLeft = inorder.slice(0, index);
  var inorderRight = inorder.slice(index + 1);
  var postorderLeft = postorder.slice(0, index);
  var postorderRight = postorder.slice(index, -1);
  var root = new TreeNode(rootVal);
  if (inorderLeft.length > 0) {
    root.left = helper(inorderLeft, postorderLeft);
  }
  if (postorderRight.length > 0) {
    root.right = helper(inorderRight, postorderRight);
  }
  return root;
}

var buildTree = function (inorder, postorder) {
  if (inorder.length == 0 || postorder.length == 0) {
    return [];
  }
  return helper(inorder, postorder);
};

console.log(buildTree([9, 3, 15, 20, 7], [9, 15, 7, 20, 3]))