leetcode 889.Construct Binary Tree from Preorder and Postorder Traversal（python）

語言: CN / TW / HK
時間 2021-11-20 10:15:08

「這是我參與11月更文挑戰的第20天，活動詳情檢視：2021最後一次更文挑戰」

描述

Given two integer arrays, preorder and postorder where preorder is the preorder traversal of a binary tree of distinct values and postorder is the postorder traversal of the same tree, reconstruct and return the binary tree.

If there exist multiple answers, you can return any of them.

Example 1:

Input: preorder = [1,2,4,5,3,6,7], postorder = [4,5,2,6,7,3,1]
Output: [1,2,3,4,5,6,7]

Example 2:

Input: preorder = [1], postorder = [1]
Output: [1]

Note:

1 <= preorder.length <= 30
1 <= preorder[i] <= preorder.length
All the values of preorder are unique.
postorder.length == preorder.length
1 <= postorder[i] <= postorder.length
All the values of postorder are unique.
It is guaranteed that preorder and postorder are the preorder traversal and postorder traversal of the same binary tree.

解析

根據題意，給定兩個整數陣列，preorder 和 postorder ，其中 preorder 是不同值的二叉樹的前序遍歷， postorder 是同一棵樹的後序遍歷，重構並返回二叉樹。如果存在多個答案，要求可以返回其中任何一個。遇到樹的問題直接深度優先遍歷 DFS 即可解決各種疑難雜症。

使用一個 preorder 和一個 postorder 重構還原一個二叉樹要找到其中的規律，從例子一種我們可以看出來：

  • 根結點是 postorder 的最後一個元素 1 ，將其從 postorder 彈出
  • 右子樹的根節點為 3 ，其在 preorder 索引為 i ，右子樹的節點包含了 preorder[i:]
  • 左子樹的節點包含了 preorder[1:i]

不斷遞迴進行上述過程，即可得到重構的二叉樹，這個題還是相對來說比較簡單。

解答

class TreeNode(object):
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
class Solution(object):
    def constructFromPrePost(self, preorder, postorder):
        """
        :type preorder: List[int]
        :type postorder: List[int]
        :rtype: TreeNode
        """
        def dfs(pre, post):
            if not pre:
                return None
            if len(pre)==1:
                return TreeNode(post.pop())
            node = TreeNode(post.pop())
            idx = pre.index(post[-1])
            node.right = dfs(pre[idx:], post)
            node.left = dfs(pre[1:idx], post)
            return node
        return dfs(preorder, postorder)

執行結果

Runtime: 40 ms, faster than 75.96% of Python online submissions for Construct Binary Tree from Preorder and Postorder Traversal.
Memory Usage: 13.8 MB, less than 5.77% of Python online submissions for Construct Binary Tree from Preorder and Postorder Traversal.

原題連結：http://leetcode.com/problems/construct-binary-tree-from-preorder-and-postorder-traversal/

您的支援是我最大的動力

「」
「」