Tree1｜Месяц тем Go

Go

[Месяц изучения темы Golang] Чистить вопросы намного лучше, чем играть в игры, и чувство достижения становится все сильнее и сильнее Я настаиваю на том, чтобы чистить один вопрос каждый день, заниматься по 30 минут каждый день, ждать 8 кубиков пресса и дождитесь большого заводского предложения.

😄

 \color{red}{~}

Я считаю, что если вы сталкиваетесь с этим вопросом в интервью, то он должен быть логически ясным, правильно сформулированным и разорванным по рукам.

Там должно быть больше, чем часть интервьюируемых.

Друзья, которые не знакомы с деревьями, могут взглянуть на предыдущие базовые обучающие вопросы!

leetcode 98. Проверка бинарных деревьев поиска

Учитывая бинарное дерево, определите, является ли оно допустимым бинарным деревом поиска.

Предположим, что бинарное дерево поиска имеет следующие характеристики:

Левое поддерево узла содержит только числа, меньшие, чем текущий узел.

Правое поддерево узла содержит только числа, большие, чем текущий узел.

Все левые и правые поддеревья сами должны быть бинарными деревьями поиска.

Пример 1:

图片.png

Пример 2:

图片.png

Код ссылки

определить дерево

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int          // 根
 *     Left *TreeNode   //左节点
 *     Right *TreeNode  //右节点
 * }
 */

языковая версия ГОрекурсия

  1. Чтобы знать, что это дерево, оно выражается только в виде массива

func isValidBST(root *TreeNode) bool {
    return helper(root, math.MinInt64, math.MaxInt64)
}

func helper(root *TreeNode, lower, upper int) bool {
    if root == nil {
        return true
    }
    if root.Val <= lower || root.Val >= upper {
        return false
    }
    return helper(root.Left, lower, root.Val) && helper(root.Right, root.Val, upper)
}

Мы знаем, что бинарное дерево поиска "Неупорядоченный обход«Последовательность полученных значений должна быть в порядке возрастания, что говорит о том, что мы можем в реальном времени проверять, больше ли значение текущего узла, чем значение узла, пройденного при предыдущем обходе по порядку в реальном времени. Если он больше, это означает, что последовательность находится в возрастающем порядке, и все дерево является двоичным деревом поиска. В противном случае это не так. В следующем коде мы используем стек для имитации процесса упорядоченного поиска. обход.

func isValidBST(root *TreeNode) bool {
    stack := []*TreeNode{}
    inorder := math.MinInt64
    for len(stack) > 0 || root != nil {
        for root != nil {
            stack = append(stack, root)
            root = root.Left
        }
        root = stack[len(stack)-1]
        stack = stack[:len(stack)-1]
        if root.Val <= inorder {
            return false
        }
        inorder = root.Val
        root = root.Right
    }
    return true
}

Искренне благодарю красивых и красивых девушек за то, что смогли это увидеть.Если эта статья будет хорошо написана, если вы почувствуете, что есть что-то

Ставьте лайк 👍 Подписывайтесь ❤️ Делитесь 👥 Мне очень полезно с 8 пакетами пресса! ! !

Если в этом блоге есть какие-либо ошибки, пожалуйста, критикуйте и советуйте, это очень ценится! ❤️❤️❤️❤️

Категории