Leetcode - Construct Binary Search Tree from Preorder Traversal

violet posted @ Apr 21, 2020 02:51:31 AM in 算法 with tags Algorithm Golang tree , 224 阅读

https://leetcode.com/problems/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:

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

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func bstFromPreorder(preorder []int) *TreeNode {
    return constructor(preorder, 0, len(preorder)-1)
}

func constructor(nums []int, left, right int) *TreeNode {
    if left == right {
        return &TreeNode{Val: nums[left]}
    }
    root := &TreeNode{Val: nums[left]}
    var i int
    for i = left+1; i <= right && nums[i] < nums[left]; i++ {
    }
    if left + 1 != i {
        root.Left = constructor(nums, left+1, i-1)
    }
    if right + 1 != i {
        root.Right = constructor(nums, i, right)
    }
    
    return root
}