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