Go 中不一致的追加行为？

Question

我正在编写一个返回二叉树节点值的垂直顺序遍历的函数。（即，从上到下，逐列）。这是预期输入和输出的示例：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   2Output:[  [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}本质上，我使用散列映射来跟踪具有相同水平距离的节点，并将它们附加到数组中。我想弄清楚的是我的输出如何与9and 一起正常工作5而不与8and一起工作2？非常感谢任何反馈！

Answer 1

我没有任何关系append。

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

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

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

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