思路
递归很简单,但是递归的时候要想到递归的三要素:确定递归函数的参数和返回值,确定终止条件,确定单层递归的逻辑。
// 递归法 // 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 }
欢迎分享,转载请注明来源:内存溢出
评论列表(0条)