Go 语言中的追加操作存在不一致性？

欢迎各位小伙伴来到golang学习网，相聚于此都是缘哈哈哈！今天我给大家带来《Go 语言中的追加操作存在不一致性？》，这篇文章主要讲到等等知识，如果你对Golang相关的知识非常感兴趣或者正在自学，都可以关注我，我会持续更新相关文章！当然，有什么建议也欢迎在评论留言提出！一起学习！

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

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] 尽管相似但并非如此，所以我不太确定从这里去哪里。 p>

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

解决方案

我和append没有任何关系。

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

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

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

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

终于介绍完啦！小伙伴们，这篇关于《Go 语言中的追加操作存在不一致性？》的介绍应该让你收获多多了吧！欢迎大家收藏或分享给更多需要学习的朋友吧~golang学习网公众号也会发布Golang相关知识，快来关注吧！