剑指offer —— 重建二叉树

[pigpigever]

点击查看原文 点击查看原题

题目

输入某二叉树的前序遍历和中序遍历的结果，请重建该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。

例如，给出

前序遍历 preorder = [3,9,20,15,7] 中序遍历 inorder = [9,3,15,20,7]

返回如下的二叉树：

    3
   / \
  9  20
    /  \
   15   7

解题思路

• 前序遍历：每次先遍历二叉树的根节点，然后再分别遍历二叉树的左右子树
• 中序遍历：每次先遍历二叉树的左子树，然后再遍历根节点，最后遍历右子树

结合以上特点，preorder 数组中的第一个值 val 为二叉树的根节点。与之对应的是，我们需要找到 val 在 inorder 数组中的位置 inorderIndex，其中 $[0, inorderIndex - 1]$ 之间的数字分布在左子树，$[inorderIndex + 1, N]$ 之间的数字在右子树；当然，我们还需要找到 preorder 数组中的所有关于左子树的值的分布和所有关于右子树的值的分布，其中 $[1, left + 1]$ 之间的数字分布在左子树，$[right, N]$ 之间的数字分布在右子树。
对于以上推论，我们只要递归的进行下去，这颗树就能被完整的构建出来了。

代码

/**
 * @param {number[]} preorder
 * @param {number[]} inorder
 * @return {TreeNode}
 */
var buildTree = function(preorder, inorder) {
    if (!preorder.length || !inorder.length) {
        return null
    }
    // 根节点的值为 preoder[0]
    const root = new TreeNode(preorder[0])
    // 找到根节点的值在 inorder 中的位置
    // 我们借此来划分 inorder 中分布在左右子树的值
    const inorderIndex = inorder.indexOf(preorder[0])
    // 找到 inorder 中左右子树的边界的值
    // 当然在 preorder 中它们对应左右子树的边界
    // 我们借此来划分 preoder 中分布在左右子树的值
    const left = preorder.indexOf(inorder[inorderIndex - 1])
    const right = preorder.indexOf(inorder[inorderIndex - 1]) + 1
    // 递归构建左右子树
    root.left = buildTree(preorder.slice(1, left + 1), inorder.slice(0, inorderIndex))
    root.right = buildTree(preorder.slice(right), inorder.slice(inorderIndex + 1))
    // 返回结果
    return root
};

[metroluffy]

上述实现无法通过测试用例，

// 单臂树
[1,2]
[1,2]
-----------
 1
  \
   2

稍微改进一下，

var buildTree = function(preorder, inorder) {
    if(preorder.length === 0 || inorder.length === 0) return null
    const root = new TreeNode(preorder[0])
    const i = inorder.indexOf(preorder[0])
    // 递归构建左右子树
    root.left = buildTree(preorder.slice(1, i + 1), inorder.slice(0, i))
    root.right = buildTree(preorder.slice(i + 1), inorder.slice(i + 1))
    return root
};