Заказать обход бинарного дерева｜Go Theme Month

Go

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

😄

 \color{red}{~}

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

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

leetcode 102. Обход бинарных деревьев по уровням

Учитывая бинарное дерево, верните значение узла, полученное путем обхода его в порядке уровней. (т.е. слой за слоем, посещая все узлы слева направо).

 

Пример: Бинарное дерево: [3,9,20,null,null,15,7],

图片.pngВозвращает результат обхода по уровням:

[ [3], [9,20], [15,7] ]

Послойный обход, как следует из названия, представляет собой послойный обход сверху вниз, слева направо.

А пока давайте подумаем, можно ли этого добиться с помощью стека?

Поскольку стек идет первым, последним вышел, но нам требуется обход порядка слоев, очевидно, первый пришел, первый вышел.

Затем будет использоваться структура данных очереди, потому что это первый вход, первый выход.

Код ссылки

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

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

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

  2. Возьмите дерево и добавьте корневой узел в массив.

  3. В извлеченном дереве, если левый узел не пуст, он будет добавлен в очередь дорог, а если правый узел не пуст, он также будет добавлен в очередь дорог.

4. Если очередь не пуста, всплываем первый, добавляем корневой узел в массив, возвращаемся к третьему шагу, а в прямой очереди нет элементов.

  1. Поместите корневой узел в массив.

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

func levelOrder(root *TreeNode) [][]int {
    ret := [][]int{}  // 定义一个存放遍历之后的数组
    if root == nil {
        return ret
    }
    q := []*TreeNode{root}  // 将整颗树怼进队列里
    for i := 0; len(q) > 0; i++ {
        ret = append(ret, []int{})  
        p := []*TreeNode{}
        for j := 0; j < len(q); j++ {
            node := q[j]
            ret[i] = append(ret[i], node.Val)
            if node.Left != nil {
                p = append(p, node.Left) // 
            }
            if node.Right != nil {
                p = append(p, node.Right)
            }
        }
        q = p
    }
    return ret
}











真心感谢帅逼靓女们能看到这里，如果这个文章写得还不错，觉得有点东西的话

求点赞👍 求关注❤️  求分享👥  对8块腹肌的我来说真的 非常有用！！！



如果本篇博客有任何错误，请批评指教，不胜感激 ！❤️❤️❤️❤️
Категории