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

}

本质上，我使用散列映射来跟踪具有相同水平距离的节点，并将它们附加到数组中。我想弄清楚的是我的输出如何与9and 一起正常工作5而不与8and一起工作2？非常感谢任何反馈！

Answer 1

我没有任何关系append。您正在对二叉树进行 DFS 遍历，该顺序称为该树的 DFS 顺序。问题是树的 DFS 顺序不是从上到下。您的代码2在 node 之前访问 node&nbsp;8，因此代码m[hd] = append(m[hd], t.Val)代替.&nbsp;没有什么不一致的。[2 8][8 2]要解决这个问题，您可以使用 BFS 来遍历树，或者，您可以将深度信息保存到其中m并m[hd]相应地对每个信息进行排序。一般来说，BFS 是一个更好的主意，但排序很快就可以破解。