105. 從前序與中序遍歷序列構(gòu)造二叉樹
題目來源：https://leetcode-cn.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal
題目
根據(jù)一棵樹的前序遍歷與中序遍歷構(gòu)造二叉樹。
注意:
你可以假設(shè)樹中沒有重復(fù)的元素。
例如，給出
前序遍歷 preorder = [3,9,20,15,7]
中序遍歷 inorder = [9,3,15,20,7]
返回如下的二叉樹：
3
/ \
9 20
/ \
15 7
解題思路
思路：遞歸
在這里，先講一下前序遍歷和中序遍歷的概念。
- 前序遍歷：首先訪問根節(jié)點，然后遍歷左子樹，最后遍歷右子樹。
- 中序遍歷：首先遍歷左子樹，然后訪問根節(jié)點，最后遍歷右子樹。
即是說兩者的遍歷順序分別為：
- 前序遍歷：根節(jié)點 -> 左子樹 -> 右子樹
- 中序遍歷：左子樹 -> 根節(jié)點 -> 右子樹
根據(jù)上面的順序可以看到，前序遍歷中，第一個就是根節(jié)點；而中序遍歷中，根節(jié)點的左側(cè)是左子樹，右側(cè)是右子樹。根據(jù)這個特性，先結(jié)合例子看下。
前序遍歷 preorder = [3,9,20,15,7]
中序遍歷 inorder = [9,3,15,20,7]
在這個例子當(dāng)中，前序遍歷 preorder 的第一個元素 3 即是根節(jié)點，再看中序遍歷， inorder 中 3 的左邊 [9] 即是左子樹，而右邊 [15, 20, 7] 即是右子樹。根據(jù)這個思路，就能構(gòu)造出完整的二叉樹。
這里說下具體的思路：
- 首先找到根節(jié)點（依據(jù)：前序遍歷順序，先遍歷根節(jié)點）
- 構(gòu)建根節(jié)點的左子樹（依據(jù)：中序遍歷，根節(jié)點的左側(cè)為左子樹）
- 構(gòu)建根節(jié)點的右子樹（依據(jù)：中序遍歷，根節(jié)點的右側(cè)為右子樹）
題目中，有個提示：【假設(shè)樹中沒有重復(fù)的元素】。依據(jù)這個提示，我們在前序遍歷中找到的根節(jié)點元素，可根據(jù)元素值在中序遍歷中定位它的位置。
具體的代碼實現(xiàn)如下。
代碼實現(xiàn)
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def buildTree(self, preorder: List[int], inorder: List[int]) -> TreeNode:
def build_tree(pre_left, pre_right, in_left, in_right):
"""構(gòu)建二叉樹
Args:
pre_left: 前序遍歷左邊界
pre_right: 前序遍歷右邊界
in_left: 后序遍歷左邊界
in_right: 后序遍歷右邊界
"""
# 終止條件
if in_left > in_right:
return None
# 根據(jù)前序遍歷的順序，第一個元素就是根節(jié)點
pre_root = pre_left
# 構(gòu)建根節(jié)點
root = TreeNode(preorder[pre_root])
# 因為題目提示，假設(shè)樹中沒有重復(fù)元素
# 那么根據(jù)根節(jié)點的值，在 inorder 中定位
in_root = inorder.index(root.val)
# 根據(jù)中序遍歷的訪問順序，根節(jié)點的左邊即是左子樹，右邊是右子樹
# 在這里先得到左子樹節(jié)點數(shù)目
size_left_subtree = in_root - in_left
# 構(gòu)建左子樹
# 在這里中序遍歷根節(jié)點左邊部分的節(jié)點（不包含根節(jié)點），其實就等同于前序遍歷左邊界下一位 + size_left_subtree 個節(jié)點
# 即是 in_left 到 inroot 前一位這部分節(jié)點，等同于 pre_left 的下一位開始的 size_left_subtree 個元素
root.left = build_tree(pre_left+1, pre_left+size_left_subtree, in_left, in_root-1)
# 構(gòu)建右子樹
# 此時中序遍歷根節(jié)點右邊部分的節(jié)點（不包含根節(jié)點），對應(yīng)前序遍歷左邊界 + 1 + sub_left_subtree 開始到其右邊界
root.right = build_tree(pre_left+1+size_left_subtree, pre_right, in_root + 1, in_right)
return root
size = len(inorder)
return build_tree(0, size-1, 0, size-1)
實現(xiàn)結(jié)果
實現(xiàn)結(jié)果
總結(jié)
- 首先在根據(jù)前序遍歷訪問的順序，先找到二叉樹的根節(jié)點，構(gòu)建根節(jié)點
- 因為題目說明可假設(shè)無重復(fù)元素，那么可依據(jù)上面找到根節(jié)點的值，在中序遍歷 inorder 中找到其位置。
- 依據(jù)中序遍歷的訪問順序，可確定當(dāng)前找到的根節(jié)點左側(cè)是左子樹，右側(cè)部分是右子樹
- 那么根據(jù)上面分析的情況，遞歸構(gòu)建左子樹，右子樹。
歡迎關(guān)注微信公眾號《書所集錄》
