golang binaryTree Предзаказ возвращаемое значение не верно

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

Срезы содержат ссылки на базовый массив, и если вы назначаете один срез другому, оба ссылаются на один и тот же массив.Если функция принимает аргумент среза, изменения, которые она вносит в элементы среза, будут видимы для вызывающей стороны

см. Срезы в Effective Go Срезы

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) от третьего вызова.

Чтобы это исправить, вы можете просто удалить передачу результирующего фрагмента в рекурсивную функцию.Функция должна создавать результирующий срез только для узла, на котором она находится, плюс для его деревьев-потомков, ей не нужно знать, каковы результаты родительского элемента.