leetcode-1008-Construct-Binary-Search-Tree-from-Preorder-Traversal

发表于   |  

描述

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]

preOrder

Note:

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

分析

题意是根据先序遍历，返回 BST，用数组表示。
题目中的提示已经够明显了，在二叉搜索树中，左子树都比根节点小，首先先序遍历第一个遍历的是根节点，往后找第一个大于根节点的节点，就是右子树开始的节点，根据这种方式递归就行了。

解决方案1(Python)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
    def bstFromPreorder(self, preorder: List[int]) -> TreeNode:
        if not preorder:
            return None
        root = TreeNode(preorder[0])
        len_of_tree = len(preorder)
        i = 1
        while i < len_of_tree:
            if preorder[i] > preorder[0]:
                break
            i += 1
        
        root.left = self.bstFromPreorder(preorder[1:i])
        root.right = self.bstFromPreorder(preorder[i:])
        return root

解决方案2(Golang)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
func bstFromPreorder(preorder []int) *TreeNode {
    if preorder == nil {
        return nil
    }
    if len(preorder) == 0 {
        return nil
    }
    if len(preorder) == 1 {
        return &TreeNode {
            Val: preorder[0],
        }
    }
    
    i := 1
    for i < len(preorder) {
        if preorder[i] > preorder[0] {
            break
        }
        i += 1
    }
    return &TreeNode{
        Val: preorder[0],
        Left: bstFromPreorder(preorder[1:i]),
        Right: bstFromPreorder(preorder[i:]),
    }
}

题目来源