This article has participated in the “Digitalstar Project” and won a creative gift package to challenge the creative incentive money

describe

Given an array of integers preorder, which represents the preorder traversal of a BST (i.e., binary search tree), construct the tree and return its root.

It is guaranteed that there is always possible to find a binary search tree with the given requirements for the given test cases.

A binary search tree is a binary tree where for every node, any descendant of Node.left has a value strictly less than Node.val, and any descendant of Node.right has a value strictly greater than Node.val.

A preorder traversal of a binary tree displays the value of the node first, then traverses Node.left, then traverses Node.right.

Example 1:

Input: preorder = [8,5,1,7,10,12]
Output: [8,5,10,1,7,null,12]
Copy the code

Example 2:

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

Note:

1 <= preorder.length <= 100
1 <= preorder[i] <= 10^8
All the values of preorder are unique.
Copy the code

parsing

In order to construct a tree, the root node of the tree is returned. As for the definition of binary tree and the definition of pre-order traversal, they have been explained in the problem and will not be repeated here.

At that time, I was very confused when I was trying to solve the problem. I didn’t catch the rules in the example, so I had a big head until I saw the solution of the superior person. Careful study turns out to be a problem of finding rules.

The first element must belong to the root node, and the elements that follow from the second element must belong to the left and right subtrees. The left subtree is smaller than the root node, and the right subtree is larger than the right subtree. The preceding traversal first traverses the left subtree and then traverses the right subtree. So start from the second element and find the index I that is larger than the root node. This is the root node of the right subtree. The elements of the left subtree are in the preorder[1: I] list, and the elements of the right subtree are in the preorder[I :] list.

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 bstFromPreorder(self, preorder):
        """
        :type preorder: List[int]
        :rtype: TreeNode
        """
        if not preorder: return None
        root = TreeNode(preorder[0])
        N = len(preorder)
        i = 1
        while i < N:
            if preorder[i] > root.val:
                break
            i += 1
        root.left = self.bstFromPreorder(preorder[1:i])
        root.right = self.bstFromPreorder(preorder[i:])
        return root
        	      
		
Copy the code

The results

Runtime: 25 ms, Faster than 43.13% of Python online submissions for Construct Binary Search Tree from Preorder Traversal. Given in Python online submissions for Construct Binary Search Tree from Preorder Traversal.Copy the code

parsing

It is also possible to iterate over list elements in a similar way.

  • Initialize root with preorder[0] and use stack to find root nodes of different subtrees
  • The preorder is traversed from the second element, which has two cases:

(1) If the element is smaller than stack[-1], the current element belongs to the left subtree of stack[-1], and the current node is added to the stack (2) otherwise, if the element is larger than stack[-1], then stack.pop() will find the appropriate root node. The right subtree of the root node is the current element, and the current node is added to the stack

  • Root at the end of the loop is the answer

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 bstFromPreorder(self, preorder):
        """
        :type preorder: List[int]
        :rtype: TreeNode
        """
        root = TreeNode(preorder[0])
        stack = [root]
        for value in preorder[1:]:
            if value < stack[-1].val:
                left = TreeNode(value)
                stack[-1].left = left
                stack.append(left)
            else:
                while stack and stack[-1].val<value:
                    tmp = stack.pop()
                right = TreeNode(value)
                tmp.right = right
                stack.append(right)
        return root
Copy the code

The results

Runtime: 39 ms, Faster than 5.69% of Python online submissions for Construct Binary Search Tree from Preorder Traversal. Given in Python online submissions for Construct Binary Search Tree from Preorder Traversal.Copy the code

Original link: leetcode.com/problems/co…

Your support is my biggest motivation