golang binaryTree Preorder返回值不正确

Question

我想将所有节点的值作为一个数组返回，但是返回值是错误的。

type TreeNode struct {

    Left  *TreeNode

    Right *TreeNode

    Val   int

}

type BinaryTree struct {

    Root *TreeNode

}

    func PreorderRecursion(root *TreeNode, result []int) []int {

    if root == nil {

        return nil

    }

    result = append(result, root.Val)

    res1 :=PreorderRecursion(root.Left,result)

    res2 :=PreorderRecursion(root.Right,result)

    result = append(result,res1...)

    result = append(result,res2...)

    return result

}

func TestBinaryTree_PreOrder(t *testing.T) {

    tree := BinaryTree{}

    tree.Root = &TreeNode{Val: 1}

    tree.Root.Left = &TreeNode{Val: 2}

    tree.Root.Right = &TreeNode{Val: 3}

    tree.Root.Left.Left = &TreeNode{Val: 4}

    var result []int

    result =PreorderRecursion(tree.Root,result)

    fmt.Println(result,"----")

}

正确的结果应该是：1 2 4 3

但我明白了：[1 1 2 1 2 4 1 3]

Answer 1

切片保存对底层数组的引用，如果将一个切片分配给另一个切片，则两者都引用同一个数组。如果一个函数接受一个切片参数，它对切片元素所做的更改将对调用者可见PreorderRecursion不应接受切片并对其进行更改。这是一种方法。func PreorderRecursion(root *TreeNode) []int {    if root == nil {        return nil    }    result := append([]int{}, root.Val)    res1 := PreorderRecursion(root.Left)    res2 := PreorderRecursion(root.Right)    result = append(result, res1...)    result = append(result, res2...)    return result}

Answer 2

问题源于您将result切片传递给递归调用。因此，每个递归调用都会附加上面节点的结果。你期望1 2 4 3，但是你1从第一个电话中得到，然后1 2（而不是只是2）从第二个电话中得到，然后1 2 4（而不是只是4）从第三个电话中得到。要解决此问题，您只需删除将结果切片传递给递归函数即可。该函数应该只为它所在的节点加上它的后代树创建一个结果切片，它不需要知道父节点的结果是什么。