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

文章目錄

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

1. 題目

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

1.1 示例

• 示例 1 1 1 ：
  

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

• 示例 2 2 2 ：

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

1.2 說明

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

1.3 限制

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

2. 解法一（遞回）

2.1 分析

此題和【LeetCode 二叉樹專項】從前序與中序遍歷序列構造二叉樹（105）十分類似，解答的方法也相近，下面僅給出三張示意圖：

• 如何通過 postorder 序列找到根節點對應 val 域及其在 inorder 序列中的索引；
• 如何通過根節點在 inorder 序列中的索引遞回構建根節點的左子節點；
• 如何通過根節點在 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, inorder: List[int], in_start: int, in_stop: int,
                    postorder: List[int], post_start: int, post_stop) -> Optional[TreeNode]:
        if in_start > in_stop or post_start > post_stop:
            return
        index = inorder.index(postorder[post_stop])
        root = TreeNode(postorder[post_stop])
        root.left = self._build_tree(inorder, in_start, index - 1,
                                     postorder, post_start, post_start + index - 1 - in_start)
        root.right = self._build_tree(inorder, index + 1, in_stop,
                                      postorder, post_stop - in_stop + index, post_stop - 1)
        return root

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


def main():
    inorder = [5, 2, 6, 4, 7, 1, 8, 3, 9]
    postorder = [5, 6, 7, 4, 2, 8, 9, 3, 1]
    sln = Solution()
    root = sln.build_tree(inorder, postorder)

    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)  # [1, 2, 3, 5, 4, 8, 9, None, None, 6, 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 ( h ) O(h) O(h)（其中 h h h 是樹的高度）的空間表示遞回時堆疊空間，這里 h < n h < n h<n，所以總空間復雜度為 O ( n ) O(n) O(n)，

3. 解法二（迭代）

作者： LeetCode-Solution