题目#105.从前序与中序遍历序列构造二叉树

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

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

例如，给出

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

返回如下的二叉树：

    3
   / \
  9  20
    /  \
   15   7

题目分析

题中提到，给出两个数组分别保存二叉树的前序遍历和中序遍历，如何从前序遍历和中序遍历恢复二叉树呢？
我们可以拿题中给出的二叉树分析分析：
对于下面两个数组以及二叉树的前中序遍历的定义：

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

我们可以分别将前中序遍历的两个数组分为三个部分，分别为根节点与左右子树：

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

下面说下为什么这么分：

• 前序遍历的根节点必然是第一个，所以很容易将根节点找到
  得到根节点在中序遍历中的索引index
• 中序遍历中，根节点在左右子树中间，所以根据中序遍历，我们能得到左右子节点的长度
  [9,3,15,20,7] -> [9|3|15,20,7]
  那么左子树的长度为index - 0，右子树的长度为inorder.lastIndex - index

构建二叉树

上面的分析帮我们将数组分为了左右子树和根节点，我们得到了左右子树和新的左右子树区间，递归就呼之欲出了。

递归已经使我们的老熟人了，同样还是考虑两点：

• 递归结束条件
  显然，数组中没有元素的时候，需要我们返回的二叉树就是null，那么我们可以将数组的是否有元素作为递归结束条件。为了避免数组的频繁赋值导致程序效率低下，我们使用数组和左右index的形式给出一个数组范围如a,b分别代表前序数组的左右范围，c,d分别代表中序数组的左右范围，于是，递归结束条件可以写为：if (a > b) return null
• 递归体
  既然要构造TreeNode，那就得给root赋值左右节点和根节点
  • 根节点
    val root = TreeNode(preorder[a])
  • 左右子节点
    root.left = buildTree(preorder, aLeft, bLeft, inorder, cLeft, dLeft)
root.right = buildTree(preorder, aRight, bRight, inorder, cRight, dRight)
    aLeft，bLeft等这些值按照上面的分析，可以很简单求得。

最终代码

class Solution {
    fun buildTree(preorder: IntArray, inorder: IntArray): TreeNode? {
        return buildTree(preorder, 0, preorder.lastIndex, inorder, 0, inorder.lastIndex)
    }

    private fun buildTree(preorder: IntArray, a: Int, b: Int, inorder: IntArray, c: Int, d: Int): TreeNode? {
        if (a > b) return null
        val root = TreeNode(preorder[a])
        val index = inorder.indexOf(preorder[a])
        val countLeft = index - c
        val countRight = d - index
        root.left = buildTree(preorder, a + 1, a + countLeft, inorder, c, c + countLeft - 1)
        root.right = buildTree(preorder, b - countRight + 1, b, inorder, d - countRight + 1, d)
        return root
    }
}