一派昧、題目
根據(jù)一棵樹的中序遍歷與后序遍歷構(gòu)造二叉樹黔姜。
注意:
你可以假設(shè)樹中沒有重復(fù)的元素。
例如斗锭，給出
中序遍歷 inorder = [9,3,15,20,7]
后序遍歷 postorder = [9,15,7,20,3]
返回如下的二叉樹：
3
/ \
9 20
/ \
15 7
二地淀、遞歸解法
1. 解題思路
回憶中序遍歷和后序遍歷的過(guò)程：
- 中序遍歷：左、根岖是、右
- 后序遍歷：左帮毁、右、根
- 參考經(jīng)典問(wèn)題剖析-由前序豺撑、中序遍歷序列構(gòu)造二叉樹烈疚，希望你看了之后這道題不用看答案寫出來(lái)
2. 編碼
示例代碼：
class BTreeNode(val value: Int) {
var left: BTreeNode? = null
var right: BTreeNode? = null
}
fun buildBTreeByInOrderAndPostOrder(inOrder: IntArray, postOrder: IntArray): BTreeNode? {
val inOrderIndexHashMap = mutableMapOf<Int, Int>()
inOrder.forEachIndexed { index, data ->
inOrderIndexHashMap[data] = index
}
return buildBTreeNodeByInOrderAndPostOrder(postOrder, inOrderIndexHashMap, 0, inOrder.size - 1, 0, postOrder.size - 1)
}
fun buildBTreeNodeByInOrderAndPostOrder(postOrder: IntArray, indexMap: MutableMap<Int, Int>, inLeft: Int, inRight: Int, postLeft: Int, postRight: Int): BTreeNode? {
if (inLeft > inRight) {
return null
}
//根節(jié)點(diǎn)
val root = BTreeNode(postOrder[postRight])
//通過(guò)跟節(jié)點(diǎn)的value值找在inOrder中的index
val index = indexMap[postOrder[postRight]] ?: return null
//找左子樹的在preOrder和inOrder中的左右index
//左子樹 在inOrder中的左右index
val leftChildTreeOnInOrderIndexLeft = inLeft
val leftChildTreeOnInOrderIndexRight = index -1
//左子樹 在postOrder中的左右index
val leftChildTreeOnPostOrderIndexLeft = postLeft
val leftChildTreeOnPOstOrderIndexRight = index - 1 - inLeft + postLeft
//右子樹 在inOrder中的左右index
val rightChildTreeOnInOrderIndexLeft = index + 1
val rightChildTreeOnInOrderIndexRight = inRight
//右子樹 在postOrder中的左右index
val rightChildTreeOnPostOrderIndexLeft = index - 1 - inLeft + postLeft + 1
val rightChildTreeOnPostOrderIndexRight = postRight - 1
root.right = buildBTreeNodeByInOrderAndPostOrder(postOrder, indexMap, rightChildTreeOnInOrderIndexLeft, rightChildTreeOnInOrderIndexRight, rightChildTreeOnPostOrderIndexLeft, rightChildTreeOnPostOrderIndexRight)
root.left = buildBTreeNodeByInOrderAndPostOrder(postOrder, indexMap, leftChildTreeOnInOrderIndexLeft, leftChildTreeOnInOrderIndexRight, leftChildTreeOnPostOrderIndexLeft, leftChildTreeOnPOstOrderIndexRight)
return root
}
3. 時(shí)空復(fù)雜度
時(shí)間復(fù)雜度：數(shù)組中每個(gè)值都要訪問(wèn)構(gòu)建二叉樹節(jié)點(diǎn)，所以時(shí)間復(fù)雜度為O(n)
空間復(fù)雜度：使用Hash表存儲(chǔ)根節(jié)點(diǎn)的index聪轿，需要O(n)的空間
三爷肝、總結(jié)
- 此題難度中等
- 經(jīng)典題目，關(guān)鍵是找到根節(jié)點(diǎn)、左灯抛、右子樹在前序金赦、中序序列中的index、leftIndex对嚼、rightIndex即可
leetcode傳送門：106. 從中序與后序遍歷序列構(gòu)造二叉樹
