【LeetCode 二叉樹專項】從前序與中序遍歷序列構造二叉樹（105）

文章目錄

• • 1. 題目
  • • 1.1 示例
    • 1.2 說明
    • 1.3 限制
  • 2. 解法一（遞回）
  • • 2.1 分析
    • 2.2 實作
    • 2.3 復雜度
  • 3. 解法二（迭代）

1. 題目

定一棵樹的前序遍歷 preorder 與中序遍歷 inorder ，請構造二叉樹并回傳其根節點，

1.1 示例

• 示例 1 1 1 ：
  

• 輸入： preorder = [3, 9, 20, 15, 7] ， inorder = [9, 3, 15, 20, 7]
• 輸出： [3, 9, 20, null, null, 15, 7]

• 示例 2 2 2 ：

• 輸入： preorder = [-1] ， inorder = [-1]
• 輸出： [-1]

1.2 說明

• 來源： 力扣（LeetCode）
• 鏈接： https://leetcode-cn.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal

1.3 限制

• 1 <= preorder.length <= 3000 ；
• inorder.length == preorder.length ；
• -3000 <= preorder[i], inorder[i] <= 3000 ；
• preorder 和 inorder 均無重復元素；
• inorder 均出現在 preorder ；
• preorder 保證為二叉樹的前序遍歷序列；
• inorder 保證為二叉樹的中序遍歷序列，

2. 解法一（遞回）

2.1 分析

實際上，本題和【LeetCode 二叉樹專項】最大二叉樹（654）十分類似，都是給定整數陣列，要求構造二叉樹，最簡單的方式都是通過遞回進行求解，并且在之前的那道題目中求解的核心方法簽名為：

def _maximum_binary_tree(self, nums: List[int], start: int, stop: int) -> Optional[TreeNode]:

此處給定了兩個序列，可仿照給出類似的求解方法簽名為：

def _build_tree(self, preorder: List[int], inorder: List[int],
                pre_start: int, pre_stop, in_start: int, in_stop: int) -> Optional[TreeNode]:

其中 pre_start 和 pre_stop 以及in_start 和 in_stop 表示遞回構建節點時所使用的 preorder 和 inorder 元素范圍，

然而，本題和【LeetCode 二叉樹專項】最大二叉樹（654）不同之處在于，求解后者的程序中總是可以很直接地確定子節點（或子樹）的 val 域及所需 nums 元素的范圍，對于本題就沒有那么直接了，例如：雖然根據前序遍歷的規則可以很容易知道陣列的第一個元素就是根節點的 val 取值，但是乍一看卻無從得知后續哪一部分屬于左子節點的 val 取值，哪一部分又屬于右子節點的 val 取值，

對此，可以充分結合中序遍歷的性質來間接確定，如下圖所示：

• 首先，在通過 preorder 確定根節點的 val 域之后，可以找到其對應在 inorder 中的位置；
• 接著，根據中序遍歷性質可知根節點左邊的元素都是其左子樹節點的 val 值，右邊元素都是其右子樹節點的 val 值，

接著，在確定根節點的左子節點時，最重要是要確定 pre_start 和 pre_stop 以及in_start 和 in_stop 的最新一組值，結合上述分析，可得遞回呼叫時確定 preorder 和 inorder 元素范圍的索引如下圖所示：

同理，在確定根節點的右子節點時，可得遞回呼叫時確定 preorder 和 inorder 元素范圍的索引如下圖所示：

2.2 實作

from collections import deque
from typing import List, Optional


class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right


class Solution:
    def _build_tree(self, preorder: List[int], inorder: List[int],
                    pre_start: int, pre_stop, in_start: int, in_stop: int) -> Optional[TreeNode]:
        if pre_start > pre_stop or in_start > in_stop:
            return
        index = inorder.index(preorder[pre_start], in_start, in_stop + 1)
        root = TreeNode(preorder[pre_start])
        root.left = self._build_tree(preorder, inorder,
                                     pre_start + 1, pre_start + index - in_start,
                                     in_start, index - 1)
        root.right = self._build_tree(preorder, inorder,
                                      pre_start + index - in_start + 1, pre_stop,
                                      index + 1, in_stop)
        return root

    def build_tree(self, preorder: List[int], inorder: List[int]) -> TreeNode:
        return self._build_tree(preorder, inorder, 0, len(preorder) - 1, 0, len(inorder) - 1)


def main():
    preorder = [3, 9, 20, 15, 7]
    inorder = [9, 3, 15, 20, 7]
    sln = Solution()
    root = sln.build_tree(preorder, inorder)

    tree = []
    visiting = deque([root])
    while visiting:
        node = visiting.popleft()
        if node:
            tree.append(node.val)
            visiting.append(node.left)
            visiting.append(node.right)
        else:
            tree.append(None)

    while True:
        if not tree[-1]:
            tree.pop()
        else:
            break

    print(tree)  # [3, 9, 20, None, None, 15, 7]


if __name__ == '__main__':
    main()

2.3 復雜度

• 時間復雜度： O ( n ) O(n) O(n)，其中 n n n 是樹中的節點個數，
• 空間復雜度： O ( n ) O(n) O(n)，除去回傳的答案需要的 O ( n ) O(n) O(n) 空間之外，我們還需要使用 O ( n ) O(n) O(n) 的空間存盤哈希映射，以及 O ( h ) O(h) O(h)（其中 h h h 是樹的高度）的空間表示遞回時堆疊空間，這里 h < n h<n h<n，所以總空間復雜度為 O ( n ) O(n) O(n) ，

3. 解法二（迭代）

• 作者： LeetCode-Solution