1008. Construct Binary Search Tree from Preorder Traversal

Stanislav Gumeniuk включен в Leetcode Leetcode-Problem

2020-05-24 253 слов 2 минуты

Содержание

Решение задачи 1008 “Construct Binary Search Tree from Preorder Traversal” с LeetCode.

Условие задачи

Вернуть корневой узел бинарного дерева созданного из массива прямого обхода

пример

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

Ограничения

1 <= preorder.length <= 100
1 <= preorder[i] <= 10^8
The values of preorder are distinct.

Решение

Обход массива и добавление элемента в дерево

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func bstFromPreorder(preorder []int) *TreeNode {
    if len(preorder) == 0 {
        return nil
    }
    
    root := TreeNode{
        Val: preorder[0],
    }
    
    for idx:=1;idx<len(preorder);idx++ {
        helper(&root, preorder[idx])
    }
    
    return &root
    
}

func helper(root *TreeNode, idx int)  {
    if idx<root.Val  {
        if root.Left == nil {
            root.Left= &TreeNode{
                Val: idx,
            }
        } else {
            helper(root.Left, idx)
        }
    } else  {
        if root.Right == nil {
            root.Right= &TreeNode{
                Val: idx,
            }
        } else {
            helper(root.Right, idx)
        }
    }   
}

Обход pre-order массива

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func bstFromPreorder(preorder []int) *TreeNode {
    cur := 0
    return helper(preorder, 0, 1<<31 - 1, &cur)
}

func helper(preorder []int, prev int, max int, cur *int) *TreeNode{
    if len(preorder) == 0 {
        return nil
    }
    if *cur == len(preorder) {
        return nil
    }
    if preorder[*cur]> max {
        return nil
    }
    root := &TreeNode {
        Val: preorder[*cur],
    }
 
    *cur++
    
    root.Left = helper(preorder, root.Val, root.Val, cur)
    root.Right = helper(preorder, root.Val, max, cur)
    
    
    
    return root
}