Go中的追加行为不一致？

Question

I'm writing a function that returns the vertical order traversal of a binary tree's node values. (ie, from top to bottom, column by column). Here's an example of expected input and output:

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

My function outputs everything as expected except for [8,2]—I'm getting [2,8] instead:

[[4] [9 5] [3 0 1] [2 8] [7]]

This is what my function looks like:

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
}

Essentially, I'm using a hash map to keep track of nodes with the same horizontal distance, and appending them to an array. What I'm trying to figure out is how come my output works properly with 9 and 5 but not with 8 and 2? Any feedback is much appreciated!

Steps to reproduce

Run the code below. You'll get an output of [[4] [9 5] [3 0 1] [2 8] [7]]; the output should be [[4] [9 5] [3 0 1] [8 2] [7]]. The thing that's tripping me up is [9 5] is appending in the correct, vertical order, whereas [2 8] is not despite being similar, so I'm not too sure where to go from here.

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

I has nothing to do with append.

You are doing a DFS-traversal of a binary tree, the order is called DFS-order of that tree. Thing is that the DFS-order of the tree is not from top to bottom.

Your code visit node 2 before node 8, so the code m[hd] = append(m[hd], t.Val) makes [2 8] instead of [8 2]. There is nothing inconsistent.

To fix the problem, you can either use a BFS to traverse the tree, or, you can keep the depth info into m and sort each m[hd] accordingly.

Generally speaking, BFS is a better idea, but a sort is quickly hackable.