題目描述
根據(jù)一棵樹的前序遍歷與中序遍歷構(gòu)造二叉樹。
注意:
你可以假設(shè)樹中沒有重復(fù)的元素。
例如，給出
前序遍歷 preorder = [3,9,20,15,7]
中序遍歷 inorder = [9,3,15,20,7]
返回如下的二叉樹：
3
/ \
9 20
/ \
15 7
解答方法
方法一：遞歸
思路
先來了解一下前序遍歷和中序遍歷是什么。
前序遍歷：遍歷順序?yàn)?父節(jié)點(diǎn) -> 左子節(jié)點(diǎn) -> 右子節(jié)點(diǎn)
后續(xù)遍歷：遍歷順序?yàn)?左子節(jié)點(diǎn) -> 父節(jié)點(diǎn) -> 右子節(jié)點(diǎn)
我們可以發(fā)現(xiàn)：前序遍歷的第一個(gè)元素為根節(jié)點(diǎn)，而在后序遍歷中，該根節(jié)點(diǎn)所在位置的左側(cè)為左子樹，右側(cè)為右子樹。
例如在例題中：
前序遍歷 preorder = [3,9,20,15,7]
中序遍歷 inorder = [9,3,15,20,7]
preorder 的第一個(gè)元素 3 是整棵樹的根節(jié)點(diǎn)。inorder 中 3 的左側(cè) [9] 是樹的左子樹，右側(cè) [15, 20, 7] 構(gòu)成了樹的右子樹。
所以構(gòu)建二叉樹的問題本質(zhì)上就是：
1、找到各個(gè)子樹的根節(jié)點(diǎn) root
2、構(gòu)建該根節(jié)點(diǎn)的左子樹
3、構(gòu)建該根節(jié)點(diǎn)的右子樹
代碼
class Solution:
def buildTree(self, preorder: List[int], inorder: List[int]) -> TreeNode:
if len(preorder) == 0:
return None
# 前序遍歷第一個(gè)值為根節(jié)點(diǎn)
root = TreeNode(preorder[0])
# 因?yàn)闆]有重復(fù)元素，所以可以直接根據(jù)值來查找根節(jié)點(diǎn)在中序遍歷中的位置
i = inorder.index(preorder[0])
# 構(gòu)建左子樹
root.left = self.buildTree(preorder[1:i+1], inorder[:i])
# 構(gòu)建右子樹
root.right = self.buildTree(preorder[i+1:], inorder[i+1:])
return root
