前序二叉树遍历失败

Question

我在旅行中遇到了等效二叉树练习的问题。

我编写了一个 Walker() 函数以按节点-左右顺序遍历树，然后使用 Same() 函数测试两个相同的二叉树是否等价。

这是我的代码的链接：https ://go.dev/play/p/vakNgx_CD3L

请参阅链接的代码中的评论。出于某种原因，使用这种遍历顺序，等价性测试在应该工作时失败了。不过，将顺序切换为左节点右或右节点左是可行的。

打印输出也让我感到困惑。这是运行时的结果。为什么遍历树 1 的前 10 个数字与遍历树 2 的第二组 10 个数字不匹配？

10

5

3

1

2

4

7

6

9

8

7

4

2

1

3

5

6

9

8

10

false

false

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我希望这有帮助 ：）。