889. Construct Binary Tree from Preorder and Postorder Traversal

🟠   🔖  树 数组 哈希表 分治 二叉树  🔗 LeetCode

题目

Given two integer arrays, preorder and postorder where preorder is the preorder traversal of a binary tree of distinct values and postorder is the postorder traversal of the same tree, reconstruct and return the binary tree.

If there exist multiple answers, you can return any of them.

Example 1:

Input: preorder = [1,2,4,5,3,6,7], postorder = [4,5,2,6,7,3,1]

Output: [1,2,3,4,5,6,7]

Example 2:

Input: preorder = [1], postorder = [1]

Output: [1]

Constraints:

• 1 <= preorder.length <= 30
• 1 <= preorder[i] <= preorder.length
• All the values of preorder are unique.
• postorder.length == preorder.length
• 1 <= postorder[i] <= postorder.length
• All the values of postorder are unique.
• It is guaranteed that preorder and postorder are the preorder traversal and postorder traversal of the same binary tree.

题目大意

给定一棵无重复值二叉树的前序遍历结果 preorder 和后序遍历结果 postorder，构造出该二叉树并返回其根节点。如果存在多个答案，则可以返回其中任意一个。

解题思路

做这道题之前，建议做一下 105. 从前序与中序遍历序列构造二叉树 和 106. 从中序与后序遍历序列构造二叉树 这两道题。

构建二叉树的套路很简单，先找到根节点，然后找到并递归构造左右子树即可。

这道题让用后序遍历和前序遍历结果还原二叉树，和前两道题有一个本质的区别：

通过前序中序，或者后序中序遍历结果，可以确定一棵原始二叉树，可以通过前序或者后序遍历结果找到根节点，然后根据中序遍历结果确定左右子树。

但是通过前序后序遍历结果，无法确定原始二叉树。可以确定根节点，但是无法确切的知道左右子树有哪些节点。题目也说了，如果有多种结果，可以返回任意一种。

具体算法是：

1. 首先把前序遍历结果的第一个元素或者后序遍历结果的最后一个元素确定为根节点的值。
2. 然后把前序遍历结果的第二个元素作为左子树的根节点的值。
3. 在后序遍历结果中寻找左子树根节点的值，从而确定了左子树的索引边界，进而确定右子树的索引边界，递归构造左右子树即可。

代码

/**
 * @param {number[]} preorder
 * @param {number[]} postorder
 * @return {TreeNode}
 */
var constructFromPrePost = function (preorder, postorder) {
  if (preorder.length == 0) return null;
  let root = new TreeNode(preorder[0]);
  for (let i = 0; i < preorder.length; i++) {
    if (postorder[i] == preorder[1]) {
      root.left = constructFromPrePost(
        preorder.slice(1, i + 2),
        postorder.slice(0, i + 1)
      );
      root.right = constructFromPrePost(
        preorder.slice(i + 2),
        postorder.slice(i + 1, postorder.length - 1)
      );
      break;
    }
  }
  return root;
};