【LeetCode】144. 二叉树的前序遍历（递归法）（错题2刷）

思路
递归很简单，但是递归的时候要想到递归的三要素：确定递归函数的参数和返回值，确定终止条件，确定单层递归的逻辑。

// 递归法

 // 1. 参数和返回值：root *TreeNode，表示当前节点，order []int，表示前序遍历序列，无返回值；
 // 2. 终止条件：当前节点为空时返回；
 // 3. 单层递归逻辑：前序遍历，即中左右，我们也是同样的逻辑，然后在中进行节点的记录，左右进入下一层。

func preOrder(root * TreeNode, order *[]int) {
    // 中
    if root == nil {
        return 
    } else {
        *order = append(*order, root.Val)
    }
    // 左
    preOrder(root.Left, order)
    // 右
    preOrder(root.Right, order)
}
func preorderTraversal(root *TreeNode) []int {
    res := []int{}
    preOrder(root, &res)
    return res
}

总结
这里遇到了一个坑，我刚开始传递的是order []int，没有加*，但是返回的是空数组，我想的切片不就是引用类型吗，怎么改不了呢？
然后我才发现[]int{}返回的并不是指针，而是数组首地址，对于c来说，这就是指针了，可以进行传递，并基于此
基于此我改为下面这种形式，new是返回的指针，它等价于&[]int{}，而我也试了一下make([]int, 0)，这是不行的，因为它也是返回的切片本身即[]int，而不是*[]int。
查阅资料发现默认情况下Golang的数组传递是值传递，所以想要修改原数组需用引用类型，即指针操作。
改用下面这样也是可以的。

func preOrder(root * TreeNode, order *[]int) {
    // 中
    if root == nil {
        return 
    } else {
        *order = append(*order, root.Val)
    }
    // 左
    preOrder(root.Left, order)
    // 右
    preOrder(root.Right, order)
}
func preorderTraversal(root *TreeNode) []int {
    res := new([]int)
    preOrder(root, res)
    return *res
}