Максимальная глубина бинарного дерева | Месяц темы Go

Go

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

😄

 \color{red}{~}

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

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

leetcode 104. Максимальная глубина бинарного дерева

Для заданного бинарного дерева найти его максимальную глубину.

Глубина бинарного дерева — это количество узлов на самом длинном пути от корневого узла до самого дальнего листового узла.

Объяснение: Листовой узел — это узел, у которого нет дочерних узлов.

Пример: Учитывая бинарное дерево [3,9,20,null,null,15,7], вернуть его максимальную глубину 3 .

图片.png

Если известны максимальные глубины ll и rr левого и правого поддеревьев, то максимальная глубина бинарного дерева равна

max(l,r)+1

Таким же образом можно вычислить максимальную глубину левого поддерева и правого поддерева. Следовательно, мы можем использовать метод «поиска в глубину» для вычисления максимальной глубины бинарного дерева. В частности, при вычислении максимальной глубины текущего бинарного дерева вы можете сначала рекурсивно вычислить максимальную глубину его левого и правого поддеревьев, а затем вычислить максимальную глубину текущего бинарного дерева за время O(1). Рекурсия завершается, когда достигается пустой узел.

Код ссылки

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

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

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

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

    Рекурсия непосредственно к самому левому и самому правому, в зависимости от того, что больше.

func maxDepth(root *TreeNode) int {
    if root == nil {
        return 0
    }
    return max(maxDepth(root.Left), maxDepth(root.Right)) + 1  // 1.
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

Итерационная версия

  1. Определить очередь (первым пришел, первым вышел)

  2. Поместите все дерево в очередь

  3. Получить длину очереди, чтобы определить, пуста ли она

  4. Определяем длину очереди

  5. удалить элемент из очереди

  6. Если элементы в очереди не пусты, они будут продолжать добавляться в очередь.

  7. Если элемент в очереди не пуст, он продолжит добавляться в очередь

  8. Так как на шаге 5 вынимается элемент, то уменьшаем один элемент, когда элемент = 0, возвращаемся к шагу 3, повторно получаем длину очереди и добавляем к глубине 1, не возвращаясь ни разу.

  9. Глубина плюс 1.

func maxDepth(root *TreeNode) int {
    if root == nil {
        return 0
    }
    queue := []*TreeNode{}   // 1.
    queue = append(queue, root)   // 2. 
    ans := 0
    for len(queue) > 0 {  // 3. 
        sz := len(queue)
        for sz > 0 {  // 4. 
            node := queue[0]  // 5. 
            queue = queue[1:]  
            if node.Left != nil {  // 6. 
                queue = append(queue, node.Left)
            }
            if node.Right != nil {  // 7.
                queue = append(queue, node.Right)
            }
            sz--   // 8.
        }
        ans++  // 9.
    }
    return ans
}

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

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

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

Категории