Go 中不一致的追加行为？

Question

我正在编写一个函数，该函数 returns 二叉树节点值的垂直顺序遍历。（即，从上到下，逐列）。这是预期输入和输出的示例：

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))
}

Answer 1

我与append无关。

你正在对一棵二叉树进行 DFS 遍历，顺序称为该树的 DFS 顺序。问题是树的 DFS 顺序不是从上到下。

您的代码在节点 8 之前访问节点 2，因此代码 m[hd] = append(m[hd], t.Val) 使 [2 8] 而不是 [8 2]。没有什么不一致的。

要解决这个问题，您可以使用 BFS 遍历树，或者，您可以将深度信息保存在 m 中并相应地对每个 m[hd] 进行排序。

一般来说，BFS 是一个更好的主意，但排序很快就可以破解。

Go 中不一致的追加行为？

Inconsistent append behavior in Go?

binary-tree

go

tree-traversal

重现步骤