4. 从中序与后序遍历序列构造二叉树（106）

一、题目内容 中等

给定两个整数数组 inorder 和 postorder ，其中 inorder 是二叉树的中序遍历， postorder 是同一棵树的后序遍历，请你构造并返回这颗 二叉树 。

示例1：

输入：inorder = [9,3,15,20,7], postorder = [9,15,7,20,3] 输出：[3,9,20,null,null,15,7]

示例2：

输入：inorder = [-1], postorder = [-1] 输出：[-1]

提示:

• 1 <= inorder.length <= 3000
• postorder.length == inorder.length
• -3000 <= inorder[i], postorder[i] <= 3000
• inorder 和 postorder 都由 不同 的值组成
• postorder 中每一个值都在 inorder 中
• inorder 保证是树的中序遍历
• postorder 保证是树的后序遍历

二、解题思路

首先回忆一下如何根据两个顺序构造一个唯一的二叉树，相信理论知识大家应该都清楚，
就是以 后序数组的最后一个元素为切割点，先切中序数组，根据中序数组，反过来在切后序数组。
一层一层切下去，每次后序数组最后一个元素就是节点元素。

说到一层一层切割，就应该想到了递归。
来看一下一共分几步：

• 第一步：如果数组大小为零的话，说明是空节点了。
• 第二步：如果不为空，那么取后序数组最后一个元素作为节点元素。
• 第三步：找到后序数组最后一个元素在中序数组的位置，作为切割点
• 第四步：切割中序数组，切成中序左数组和中序右数组 （顺序别搞反了，一定是先切中序数组）
• 第五步：切割后序数组，切成后序左数组和后序右数组
• 第六步：递归处理左区间和右区间

var buildTree = function (inorder, postorder) {
  // 第一步
  if (!postorder.length) return null
  // 第二步：后序遍历数组最后一个元素，就是当前的中间节点
  const nodeVal = postorder[postorder.length - 1]
  const node = new TreeNode(nodeVal)
  // 当该节点是叶子节点，直接返回
  if (postorder.length === 1) return root
  // 第三步：找切割点
  const mid = inorder.indexOf(nodeVal)
  // 第四步：切割中序数组，得到 中序左数组和中序右数组
  // 第五步：切割后序数组，得到 后序左数组和后序右数组
  // 第六步
  root.left = buildTree(中序左数组，后序左数组)
  root.right = buildTree(中序右数组，后序右数组)
  return root
};

难点大家应该发现了，就是如何切割，以及边界值找不好很容易乱套。
此时应该注意确定切割的标准，是左闭右开，还有左开又闭，还是左闭又闭，这个就是不变量，要在递归中保持这个不变量。
在切割的过程中会产生四个区间，把握不好不变量的话，一会左闭右开，一会左闭又闭，必然乱套！

首先要切割中序数组，为什么先切割中序数组呢？
切割点在后序数组的最后一个元素，就是用这个元素来切割中序数组的，所以必要先切割中序数组。
中序数组相对比较好切，找到切割点（后序数组的最后一个元素）在中序数组的位置，然后切割，如下代码中坚持左闭右开的原则：

// 找到切割点
const mid = inorder.indexOf(nodeVal)
// 左闭右开区间：[0, mid)
const leftInorder = inorder.slice(0, mid)
// [mid + 1, end)
const rightInorder = inorder.slice(mid + 1)

后序数组的切割点怎么找？
后序数组没有明确的切割元素来进行左右切割，不像中序数组有明确的切割点，切割点左右分开就可以了。
此时有一个很重要的点，就是中序数组大小一定是和后序数组的大小相同的（这是必然）。
中序数组我们都切成了左中序数组和右中序数组了，那么后序数组就可以按照左中序数组的大小来切割，切成左后序数组和右后序数组。

// postorder 舍弃末尾元素，因为这个元素就是中间节点，已经用过了
postorder.pop()
// 左闭右开，使用切割后的中序数组的大小，作为切割点。[0, leftInorder.length]
const leftPostorder = postorder.slice(0, leftInorder.length)
// [leftInorder.length, end]。这里的 leftInorder.length 不加 1，因为不像中序数组需要去掉中间切割点
const rightPostorder = postorder.slice(leftInorder.length)

三、具体代码

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {number[]} inorder
 * @param {number[]} postorder
 * @return {TreeNode}
 */
var buildTree = function (inorder, postorder) {
  if (!inorder.length) return null
  const nodeVal = postorder[postorder.length - 1]
  const mid = inorder.indexOf(nodeVal)
  const root = new TreeNode(nodeVal)
  const leftInorder = inorder.slice(0, mid)
  const rightInorder = inorder.slice(mid + 1)
  postorder.pop()
  const leftPostorder = postorder.slice(0, leftInorder.length)
  const rightPostorder = postorder.slice(leftInorder.length)
  root.left = buildTree(leftInorder, leftPostorder)
  root.right = buildTree(rightInorder, rightPostorder)
  return root
};

上面的代码，每次递归，我们都需要新建数组，这样十分消耗内存。
我们使用数组下标的方式，缩小数组区间，来优化性能。

const createTree = (inorder, inorderStart, inorderEnd, postorder, postStart, postEnd) => {
  if (postStart === postEnd) return null
  const nodeVal = postorder[postEnd - 1]
  const root = new TreeNode(nodeVal)
  const mid = inorder.indexOf(nodeVal)
  if (postEnd - postStart === 1) return root
  // 分割中序数组
  // 左中序区间，左闭右开 [inorderStart, mid)
  const leftInorderStart = inorderStart 
  const leftInorderEnd = mid
  // 右中序区间，左闭右开[mid + 1, rightInorderEnd)
  const rightInorderStart = mid + 1 
  const rightInorderEnd = inorderEnd 
  // 切割后序数组
  // 左后序区间，左闭右开 [postStart, postStart + mid - inorderStart)
  const leftPostStart = postStart 
  const leftPostEnd = postStart + mid - inorderStart
  // 右后序区间，左闭右开 [postStart + mid - inorderStart, postEnd - 1)
  const rightPostStart = postStart + mid - inorderStart
  const rightPostEnd = postEnd - 1 // 减一，目的把用了的后序元素去除
  root.left = createTree(inorder, leftInorderStart, leftInorderEnd, postorder, leftPostStart, leftPostEnd)
  root.right = createTree(inorder, rightInorderStart, rightInorderEnd, postorder, rightPostStart, rightPostEnd)
  return root
}
/**
 * @param {number[]} inorder
 * @param {number[]} postorder
 * @return {TreeNode}
 */
var buildTree = function (inorder, postorder) {
  if (!inorder.length) return null
  return createTree(inorder, 0, inorder.length, postorder, 0, postorder.length)
};

四、其他解法

五、从前序与后序遍历序列构造二叉树（105）

var buildTree = function (preorder, inorder) {
  if (!preorder.length) return null
  const nodeVal = preorder.shift()
  const root = new TreeNode(nodeVal)
  const mid = inorder.indexOf(nodeVal)
  const leftInorder = inorder.slice(0, mid)
  const rightInorder = inorder.slice(mid + 1)
  const leftPreorder = preorder.slice(0, leftInorder.length)
  const rightPreorder = preorder.slice(leftInorder.length)
  root.left = buildTree(leftPreorder, leftInorder)
  root.right = buildTree(rightPreorder, rightInorder)
  return root
};