在围棋不一致的追加行为？

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
}

从本质上讲，我使用的散列映射来跟踪具有相同的水平距离的节点，并把它们附加到一个数组。我试图弄清楚是怎么来的我的输出与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-顺序不是自上而下。

节点2之前，您的代码访问节点8，所以代码m[hd] = append(m[hd], t.Val)使得[2 8]代替[8 2]。没有什么不一致。

为了解决这个问题，你可以使用一个BFS遍历树，或者，你可以保持深度信息到m和排序每个相应m[hd]。

一般来说，BFS是一个更好的主意，而是一种是快速容易被破解。