一、题目
根据一棵树的前序遍历与中序遍历构造二叉树。
注意:
你可以假设树中没有重复的元素。
示例：给出
前序遍历 preorder = [3,9,20,15,7]
中序遍历 inorder = [9,3,15,20,7]
返回如下的二叉树：
3
/ \
9 20
/ \
15 7
二、递归解法
1. 解题思路
清楚前序遍历和中序遍历的过程：
- 前序遍历：根、左、右
- 中序遍历：左、根、右
- 将前序、中序序列做如下图切割，可以看到是明显的递归调用
前序、中序序列分割图
- 前序序列中，preOrder[preLeft]为根节点，通过值找到根节点在中序序列中的index，记为pIndex。由于树中没有重复的元素，这个过程可以使用一个hash表存储index，节点值value作为hashKey，index作为hashValue
- 通过根节点分割的左右子树边界通过
preLeft、preRight、inLeft、inRight、pIndex表示，得到左右子树的前序、中序序列。其中中序遍历的左右子树的边界很容就知道是[inLeft，pIndex - 1]和[pIndex + 1, inRight]；前序遍历中，左子树的右边界比较不好一眼看出来，我们可以稍微计算一下，左子树右边界 - (preLeft + 1) = pIndex -1 - inLeft，由这个公式可得出左子树右边界 = pIndex - inLeft + preLeft，自然而然右子树的左边界就是pIndex - inLeft + preLeft + 1，所以前序遍历左右子树的边界就是[preLeft + 1, pIndex - inLeft + preLeft]和[pIndex - inLeft + preLeft + 1, preRight]。不要嫌麻烦，其实这道题关键就是边界值的表示，没有什么难的。 - 递归结束条件：preLeft > preRight，相等的时候就是叶子结点。
2. 编码
由解题思路，很容易写出此题的递归解法代码。
示例代码：
class BTreeNode(val value: Int) {
var left: BTreeNode? = null
var right: BTreeNode? = null
}
fun buildBTreeByPreOrderAndInOrder(preOrder: IntArray, inOrder: IntArray): BTreeNode? {
val inOrderIndexHashMap = mutableMapOf<Int, Int>()
inOrder.forEachIndexed { index, data ->
inOrderIndexHashMap[data] = index
}
return buildBTreeNode(preOrder, inOrderIndexHashMap, 0, preOrder.size - 1, 0, inOrder.size - 1)
}
fun buildBTreeNode(preOrder: IntArray, indexMap: MutableMap<Int, Int>, preOrderLeft: Int, preOrderRight: Int, inOrderLeft: Int, inOrderRight: Int): BTreeNode? {
if (preOrderLeft > preOrderRight) {
return null
}
//根节点
val root = BTreeNode(preOrder[preOrderLeft])
//通过跟节点的value值找在inOrder中的index
val index = indexMap[preOrder[preOrderLeft]] ?: return null
//找左子树的在preOrder和inOrder中的左右index
//左子树 在preOrder中的左右index
val leftChildTreeOnPreOrderIndexLeft = preOrderLeft + 1
val leftChildTreeOnPreOrderIndexRight = index - inOrderLeft + preOrderLeft
//左子树 在inOrder中的左右index
val leftChildTreeOnInOrderIndexLeft = inOrderLeft
val leftChildTreeOnInOrderIndexRight = index - 1
//右子树 在preOrder中的左右index
val rightChildTreeOnPreOrderIndexLeft = leftChildTreeOnPreOrderIndexRight + 1
val rightChildTreeOnPreOrderIndexRight = preOrderRight
//右子树 在inOrder中的左右index
val rightChildTreeOnInOrderIndexLeft = index + 1
val rightChildTreeOnInOrderIndexRight = inOrderRight
root.left = buildBTreeNode(preOrder, indexMap, leftChildTreeOnPreOrderIndexLeft, leftChildTreeOnPreOrderIndexRight, leftChildTreeOnInOrderIndexLeft, leftChildTreeOnInOrderIndexRight)
root.right = buildBTreeNode(preOrder, indexMap, rightChildTreeOnPreOrderIndexLeft, rightChildTreeOnPreOrderIndexRight, rightChildTreeOnInOrderIndexLeft, rightChildTreeOnInOrderIndexRight)
return root
}
3. 时空复杂度分析
时间复杂度：数组中每个值都要访问构建二叉树节点，所以时间复杂度为O(N)
空间复杂度：使用Hash表存储根节点的index，需要O(N)的空间，最多有O(logN)个函数调用，所以空间复杂度是O(N)
四、总结
- 此题难度中等
- 经典题目，关键是找到根节点、左、右子树边界分别在在前序、中序序列中的index、leftIndex、rightIndex即可
leetcode传送门：105. 从前序与中序遍历序列构造二叉树
