LeetCode 1008. Construct Binary Search Tree from Preorder Traversal

Posted on | In |
Words count in article: 261 | Reading time ≈ 1

题目

Return the root node of a binary search tree that matches the given preorder traversal.

(Recall that a binary search tree is a binary tree where for every node, any descendant of node.left has a value < node.val, and any descendant of node.right has a value > node.val. Also recall that a preorder traversal displays the value of the node first, then traverses node.left, then traverses node.right.)

Example 1:

1
2
Input: [8,5,1,7,10,12]
Output: [8,5,10,1,7,null,12]

Note:

  1. 1 <= preorder.length <= 100
  2. The values of preorder are distinct.

思路

递归。
先序遍历第一个数字即为根节点，又BST的左子树都比根节点小，而先序遍历要把左子树遍历结束才遍历右子树，所以向后找第一个大于根节点数字位置，该位置就是右子树的根节点。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    def bstFromPreorder(self, preorder):
        """
        :type preorder: List[int]
        :rtype: TreeNode
        """
        if not preorder:
            return None
        root = TreeNode(preorder[0])
        i = 1
        while i < len(preorder):
            if preorder[i] > root.val:
                break
            i += 1
        root.left = self.bstFromPreorder(preorder[1:i])
        root.right = self.bstFromPreorder(preorder[i:])
        return root