Я пишу функцию, которая возвращает вертикальный порядок значений узлов двоичного дерева.(то есть сверху вниз, столбец за столбцом).Вот пример ожидаемого ввода и вывода:
Input: [3,9,8,4,0,1,7,null,null,null,2,5] (0's right child is 2 and 1's left child is 5)
3
/\
/ \
9 8
/\ /\
/ \/ \
4 01 7
/\
/ \
5 2
Output:
[
[4],
[9,5],
[3,0,1],
[8,2],
[7]
]
Моя функция выводит все, как ожидалось, за исключением [8,2] - вместо этого я получаю [2,8]:
[[4] [9 5] [3 0 1] [2 8] [7]]
Этокак выглядит моя функция:
func verticalOrder(root *TreeNode) [][]int {
if root == nil {
return [][]int{}
}
var (
hd int
m map[int][]int
vals [][]int
min int
max int
traverse func(t *TreeNode, hd int, m map[int][]int)
)
m = make(map[int][]int)
min = 0
max = 0
traverse = func(t *TreeNode, hd int, m map[int][]int) {
if t == nil {
return
}
m[hd] = append(m[hd], t.Val)
if max < hd {
max = hd
}
if min > hd {
min = hd
}
traverse(t.Left, hd-1, m)
traverse(t.Right, hd+1, m)
}
traverse(root, hd, m)
for i := min; i <= max; i++ {
vals = append(vals, m[i])
}
return vals
}
По сути, я использую хэш-карту для отслеживания узлов с одинаковым горизонтальным расстоянием и добавляю их в массив.Я пытаюсь понять, как получается, что мой вывод работает правильно с 9 и 5, но не с 8 и 2?Любая обратная связь приветствуется!
Шаги для воспроизведения
Запустите приведенный ниже код.Вы получите вывод [[4] [9 5] [3 0 1] [2 8] [7]];вывод должен быть [[4] [9 5] [3 0 1] [8 2] [7]].Меня сбивает с толку то, что [9 5] добавляется в правильном вертикальном порядке, тогда как [2 8], несмотря на то, что он похож, поэтому я не слишком уверен, куда идти.
package main
import "fmt"
// TreeNode is a binary tree node.
type TreeNode struct {
Val int
Left *TreeNode
Right *TreeNode
}
func verticalOrder(root *TreeNode) [][]int {
if root == nil {
return [][]int{}
}
var (
hd int
m map[int][]int
vals [][]int
min int
max int
traverse func(t *TreeNode, hd int, m map[int][]int)
)
m = make(map[int][]int)
min = 0
max = 0
traverse = func(t *TreeNode, hd int, m map[int][]int) {
if t == nil {
return
}
m[hd] = append(m[hd], t.Val)
if max < hd {
max = hd
}
if min > hd {
min = hd
}
traverse(t.Left, hd-1, m)
traverse(t.Right, hd+1, m)
}
traverse(root, hd, m)
for i := min; i <= max; i++ {
vals = append(vals, m[i])
}
return vals
}
func main() {
root := &TreeNode{
Val: 3,
Left: &TreeNode{
Val: 9,
Left: &TreeNode{
Val: 4,
Left: nil,
Right: nil,
},
Right: &TreeNode{
Val: 0,
Left: nil,
Right: &TreeNode{
Val: 2,
Left: nil,
Right: nil,
},
},
},
Right: &TreeNode{
Val: 8,
Left: &TreeNode{
Val: 1,
Left: &TreeNode{
Val: 5,
Left: nil,
Right: nil,
},
Right: nil,
},
Right: &TreeNode{
Val: 7,
Left: nil,
Right: nil,
},
},
}
fmt.Println(verticalOrder(root))
}