英文:
I have two Go functions that I'd expect to behave the same, but give different results. Trying to understand why
问题
我正在为你翻译以下内容：
我在编写二叉搜索树遍历时遇到了一个问题，然后稍微改变了语法就解决了，但我不明白为什么一开始它不起作用。我提供的两个代码示例，我期望它们以完全相同的方式运行，但实际上并不是这样。
第一个示例将 curr 变量设置为其左节点 curr.left，然后递归调用 InOrderRecursive，而第二个示例直接在 curr.left 上调用 InOrderRecursive。
type BST struct {
value int
left *BST
right *BST
}
第一个示例不起作用（返回的结果不正确）：
func (tree *BST) InOrderRecursive(values []int) []int {
curr := tree
if curr.left != nil {
curr = curr.left
values = curr.InOrderRecursive(values)
}
values = append(values, curr.value)
if curr.right != nil {
curr = curr.right
values = curr.InOrderRecursive(values)
}
return values
}
第二个示例起作用（返回正确的结果）：
func (tree *BST) InOrderRecursive(values []int) []int {
curr := tree
if curr.left != nil {
values = curr.left.InOrderRecursive(values)
}
values = append(values, curr.value)
if curr.right != nil {
values = curr.right.InOrderRecursive(values)
}
return values
}
请问有人可以解释这两个代码示例的区别以及不同行为的原因吗？
英文:
I was writing a binary search tree traversal when I came across a problem, and then a slight syntax change fixed it but I don't understand why it wasn't working in the first palce. The two code examples I provide I would expect to run the exact same way but they don't.
One sets the curr variable to it's left node curr.left, then recursively calls the InOrderRecursive, while the other calls InOrderRecursive directly on curr.left itself.
type BST struct {
value int
left *BST
right *BST
}
Does not work (This does return but with the wrong values):
func (tree *BST) InOrderRecursive(values []int) []int {
curr := tree
if curr.left != nil {
curr = curr.left
values = curr.InOrderRecursive(values)
}
values = append(values, curr.value)
if curr.right != nil {
curr = curr.right
values = curr.InOrderRecursive(values)
}
return values
}
Works (returns the correct values):
func (tree *BST) InOrderRecursive(values []int) []int {
curr := tree
if curr.left != nil {
values = curr.left.InOrderRecursive(values)
}
values = append(values, curr.value)
if curr.right != nil {
values = curr.right.InOrderRecursive(values)
}
return values
}
Could someone please explain the difference in these two code examples and the reason for the different behavior?
答案1
得分: 1
第一个版本有一个小错误。如果在版本1中curr.left不是nil，那么values = append(values, curr.value)将会将左子节点的值添加到列表中，而不是当前节点的值，因为在if语句的作用域之外，curr现在等于curr.left。更具体地说，
func (tree *BST) InOrderRecursive(values []int) []int {
curr := tree
if curr.left != nil {
curr = curr.left
values = curr.InOrderRecursive(values)
}
// 如果curr.left不是nil，这里的curr将会取左子节点的值（错误）。
values = append(values, curr.value)
// 这个问题也会传递到这里（如果原始的curr.left != nil），我们现在检查的是左子节点的右子节点。
if curr.right != nil {
curr = curr.right
values = curr.InOrderRecursive(values)
}
// 右递归调用的结果没有添加到`values`列表中（错误）。
return values
}
英文:
The first version has a slight bug. If curr.left is not nil in version 1, then values = append(values, curr.value) will append the left child node's value to the list, not the current node, since curr is now equal to curr.left outside of the if scope. More specifically,
func (tree *BST) InOrderRecursive(values []int) []int {
curr := tree
if curr.left != nil {
curr = curr.left
values = curr.InOrderRecursive(values)
}
// curr here will take on the node's left child value if
// it's not nil (bug).
values = append(values, curr.value)
// That issue will cascade to here as well (if the OG curr.left
// != nil), we're now checking the left child node's right child.
if curr.right != nil {
curr = curr.right
values = curr.InOrderRecursive(values)
}
// The result of the right recursive call is not appended to the
// `values` list. (bug)
return values
}
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库，让每个人都能够通过互相帮助和分享经验来进步。
评论