前序二叉树遍历失败

Question

我在旅行中遇到了等效二叉树练习的问题。我编写了一个 Walker() 函数以按节点-左右顺序遍历树，然后使用 Same() 函数测试两个相同的二叉树是否等价。这是我的代码的链接：https ://go.dev/play/p/vakNgx_CD3L请参阅链接的代码中的评论。出于某种原因，使用这种遍历顺序，等价性测试在应该工作时失败了。不过，将顺序切换为左节点右或右节点左是可行的。打印输出也让我感到困惑。这是运行时的结果。为什么遍历树 1 的前 10 个数字与遍历树 2 的第二组 10 个数字不匹配？1053124769874213569810falsefalse

Answer 1

我认为这里的问题是，您正在使用https://pkg.go.dev/golang.org/x/tour/tree#New函数，它返回一个从 1k 到 10k 值的随机二叉树。

tree.New(1)“随机”一词在这里很重要，因此您不能期望获得与函数调用输出相同的二叉树。

尽管树节点的值从 1 到 10（在 k=1 的情况下），但返回的树的顺序将不同。如果您使用.String()函数打印树，您可以清楚地看到这一点。看看下面的游乐场代码，我在其中打印了树，它清楚地表明每次调用tree.New函数时返回的树都是不同的。 https://go.dev/play/p/WkF8frfno17

我希望这有帮助 ：）。