“This is the 20th day of my participation in the Gwen Challenge in November. Check out the details: The Last Gwen Challenge in 2021.”

describe

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 =,2,4,5,3,6,7 [1], postorder =,5,2,6,7,3,1 [4] the Output:,2,3,4,5,6,7 [1]Copy the code

Example 2:

Input: preorder = [1], postorder = [1]
Output: [1]
Copy the code

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.
Copy the code

parsing

Given two integer arrays, preorder and Postorder, preorder is the pre-traversal of a binary tree with different values, postorder is the post-traversal of the same tree, reconstructing and returning the binary tree. If more than one answer exists, it is required to return any one of them. In case of tree problems, direct depth – first traversal of DFS can solve various difficult problems.

Restoring a binary tree with a Preorder and a Postorder refactoring to find the pattern, we can see it in one example:

  • The root is the last element of the Postorder, 1, which is popped from the Postorder
  • The root node of the right subtree is 3 and its preorder index is I. The nodes of the right subtree contain preorder[I :].
  • The nodes of the left subtree contain preorder[1: I]

It’s relatively easy to recurse and get a reconstructed binary tree.

answer

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)

        	      
		
Copy the code

The results

Runtime: 40 ms, Faster than 75.96% of Python online submissions for Construct Binary Tree from Preorder and Postorder Traversal. Memory Usage: Given in Python online submissions for Construct Binary Tree from Preorder and Postorder Traversal.Copy the code

Original link: leetcode.com/problems/co…

Your support is my biggest motivation