一碌嘀、題目
根據(jù)一棵樹的前序遍歷與中序遍歷構(gòu)造二叉樹涣旨。
注意:
你可以假設(shè)樹中沒有重復(fù)的元素。
示例：給出
前序遍歷 preorder = [3,9,20,15,7]
中序遍歷 inorder = [9,3,15,20,7]
返回如下的二叉樹：
3
/ \
9 20
/ \
15 7
二筏餐、遞歸解法
1. 解題思路
清楚前序遍歷和中序遍歷的過程：
- 前序遍歷：根开泽、左、右
- 中序遍歷：左魁瞪、根穆律、右
- 將前序、中序序列做如下圖切割导俘，可以看到是明顯的遞歸調(diào)用
前序峦耘、中序序列分割圖
- 前序序列中，preOrder[preLeft]為根節(jié)點(diǎn)旅薄，通過值找到根節(jié)點(diǎn)在中序序列中的index辅髓，記為pIndex。由于樹中沒有重復(fù)的元素少梁，這個(gè)過程可以使用一個(gè)hash表存儲(chǔ)index洛口，節(jié)點(diǎn)值value作為hashKey，index作為hashValue
- 通過根節(jié)點(diǎn)分割的左右子樹邊界通過
preLeft凯沪、preRight第焰、inLeft、inRight妨马、pIndex表示挺举，得到左右子樹的前序、中序序列烘跺。其中中序遍歷的左右子樹的邊界很容就知道是[inLeft湘纵，pIndex - 1]和[pIndex + 1, inRight]；前序遍歷中滤淳，左子樹的右邊界比較不好一眼看出來梧喷，我們可以稍微計(jì)算一下，左子樹右邊界 - (preLeft + 1) = pIndex -1 - inLeft，由這個(gè)公式可得出左子樹右邊界 = pIndex - inLeft + preLeft铺敌，自然而然右子樹的左邊界就是pIndex - inLeft + preLeft + 1绊困，所以前序遍歷左右子樹的邊界就是[preLeft + 1, pIndex - inLeft + preLeft]和[pIndex - inLeft + preLeft + 1, preRight]。不要嫌麻煩适刀，其實(shí)這道題關(guān)鍵就是邊界值的表示，沒有什么難的煤蹭。 - 遞歸結(jié)束條件：preLeft > preRight笔喉，相等的時(shí)候就是葉子結(jié)點(diǎn)。
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
}
//根節(jié)點(diǎn)
val root = BTreeNode(preOrder[preOrderLeft])
//通過跟節(jié)點(diǎn)的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. 時(shí)空復(fù)雜度分析
時(shí)間復(fù)雜度：數(shù)組中每個(gè)值都要訪問構(gòu)建二叉樹節(jié)點(diǎn)，所以時(shí)間復(fù)雜度為O(N)
空間復(fù)雜度：使用Hash表存儲(chǔ)根節(jié)點(diǎn)的index稽物，需要O(N)的空間奄毡，最多有O(logN)個(gè)函數(shù)調(diào)用，所以空間復(fù)雜度是O(N)
四贝或、總結(jié)
- 此題難度中等
- 經(jīng)典題目吼过，關(guān)鍵是找到根節(jié)點(diǎn)、左咪奖、右子樹邊界分別在在前序盗忱、中序序列中的index、leftIndex羊赵、rightIndex即可
leetcode傳送門：105. 從前序與中序遍歷序列構(gòu)造二叉樹
