网上赚钱的工作_做那个的网页_seo网站推广简历_百度seo怎么把关键词优化上去

深入理解递归思想

这次我们要好好谈一谈递归，为什么很多同学看递归算法都是“一看就会，一写就废”。

主要是对递归不成体系，没有方法论，每次写递归算法 ，都是靠玄学来写代码，代码能不能编过都靠运气。

本篇将介绍前后中序的递归写法，一些同学可能会感觉很简单，其实不然，我们要通过简单题目把方法论确定下来，有了方法论，后面才能应付复杂的递归。

递：将问题拆解成子问题，子问题再拆解为子问题，直到被拆解的问题是最小的子问题。
归：最小的子问题被解决了，那么上一层的也会被解决，再上一层的也会被解决，一直到最开始的问题被解决。

递归三要素

这里帮助大家确定下来递归算法的三个要素。每次写递归，都按照这三要素来写，可以保证大家写出正确的递归算法！

1. 确定递归函数的参数和返回值： 确定哪些参数是递归的过程中需要处理的，那么就在递归函数里加上这个参数， 并且还要明确每次递归的返回值是什么，进而确定递归函数的返回类型。

2. 确定终止条件： 写完了递归算法, 运行的时候，经常会遇到栈溢出的错误，就是没写终止条件或者终止条件写的不对，操作系统也是用一个栈的结构来保存每一层递归的信息，如果递归没有终止，操作系统的内存栈必然就会溢出。

3. 确定单层递归的逻辑： 确定每一层递归需要处理的信息。在这里也就会重复调用自己来实现递归的过程。

好了，我们确认了递归的三要素，接下来就来练练手：

以下以前序遍历为例：

1. 确定递归函数的参数和返回值：因为要打印出前序遍历节点的数值，所以参数里需要传入*[]any切片来放节点的数值(注意这里传的是切片的指针，因为递归的时切片长度在不断增大，可能会扩容），除了这一点就不需要再处理什么数据了也不需要有返回值代码如下：

func traversal(root *TreeNode, res *[]T)

2. 确定终止条件：在递归的过程中，如何算是递归结束了呢，当然是当前遍历的节点是空了，那么本层递归就要结束了，所以如果当前遍历的这个节点是空，就直接return，代码如下：

if root == nil {return 
}

3. 确定单层递归的逻辑：前序遍历是中左右的顺序，所以在单层递归的逻辑，是要先取中节点的数值，代码如下：

*res = append(*res,root.Val)    // 中
traversal(root.Left, res)  // 左
traversal(root.Right, res) // 右

单层递归的逻辑就是按照中左右的顺序来处理的，这样二叉树的前序遍历，基本就写完了，再看一下完整代码：

前序遍历：

/*** Definition for a binary tree node.* type TreeNode struct {*     Val int*     Left *TreeNode*     Right *TreeNode* }*/
func preorderTraversal(root *TreeNode) []int {if root == nil {return []int{}}res := make([]int,0)// 注意res传的是指针，因为函数内部res可能扩容，所以用指针保证还能拿到原切片traversal(root,&res)return res
}func traversal(root *TreeNode,res *[]int){if root == nil {return }*res = append(*res,root.Val)traversal(root.Left,res)traversal(root.Right,res)
}

那么前序遍历写出来之后，中序和后序遍历就不难理解了，代码如下：

中序遍历：

/*** Definition for a binary tree node.* type TreeNode struct {*     Val int*     Left *TreeNode*     Right *TreeNode* }*/
func inorderTraversal(root *TreeNode) []int {if root == nil {return []int{}}res := make([]int,0)traversal(root,&res)return res
}func traversal(root *TreeNode,res *[]int)  {if root == nil {return }traversal(root.Left,res)*res = append(*res,root.Val)traversal(root.Right,res)
}

后序遍历：

/*** Definition for a binary tree node.* type TreeNode struct {*     Val int*     Left *TreeNode*     Right *TreeNode* }*/
func postorderTraversal(root *TreeNode) []int {if root == nil {return []int{}}res := make([]int,0)traversal(root,&res)return res
}func traversal(root *TreeNode,res *[]int) {if root == nil {return }traversal(root.Left,res)traversal(root.Right,res)*res = append(*res,root.Val)
}

leetcode上三道题目：

建议每种遍历方式都对着二叉数的图，深入思考或模拟一下递归时，操作系统底层的那个【函数栈】，调用一次自身就是【入栈】，当前所在层的函数执行完成后，【出栈】，回到当时调用它的位置去继续往后执行（如果是回溯法，继续往后执行大部分又是for的下一轮循环调用自己）。

144.二叉树的前序遍历

144. 二叉树的前序遍历

给你二叉树的根节点 root，返回它节点值的 前序 遍历。

示例 1：

输入：root = [1,null,2,3]输出：[1,2,3]

解释：

示例 2：

输入：root = [1,2,3,4,5,null,8,null,null,6,7,9]输出：[1,2,4,5,6,7,3,8,9]

解释：

示例 3：

输入：root = []输出：[]

示例 4：

输入：root = [1]输出：[1]

提示：

• 树中节点数目在范围 [0, 100] 内
• -100 <= Node.val <= 100

进阶：递归算法很简单，你可以通过迭代算法完成吗？

Go代码

/*** Definition for a binary tree node.* type TreeNode struct {*     Val int*     Left *TreeNode*     Right *TreeNode* }*/
func preorderTraversal(root *TreeNode) []int {if root == nil {return []int{}}res := make([]int,0)// 注意res传的是指针，因为函数内部res可能扩容，所以用指针保证还能拿到原切片traversal(root,&res)return res
}func traversal(root *TreeNode,res *[]int){if root == nil {return }*res = append(*res,root.Val)traversal(root.Left,res)traversal(root.Right,res)
}

145.二叉树的后序遍历

145. 二叉树的后序遍历

给你一棵二叉树的根节点 root ，返回其节点值的 后序遍历 。

示例 1：

输入：root = [1,null,2,3]输出：[3,2,1]

解释：

示例 2：

输入：root = [1,2,3,4,5,null,8,null,null,6,7,9]输出：[4,6,7,5,2,9,8,3,1]

解释：

示例 3：

输入：root = []输出：[]

示例 4：

输入：root = [1]输出：[1]

提示：

• 树中节点的数目在范围 [0, 100] 内
• -100 <= Node.val <= 100

进阶：递归算法很简单，你可以通过迭代算法完成吗？

Go代码

/*** Definition for a binary tree node.* type TreeNode struct {*     Val int*     Left *TreeNode*     Right *TreeNode* }*/
func postorderTraversal(root *TreeNode) []int {if root == nil {return []int{}}res := make([]int,0)traversal(root,&res)return res
}func traversal(root *TreeNode,res *[]int) {if root == nil {return }traversal(root.Left,res)traversal(root.Right,res)*res = append(*res,root.Val)
}

94.二叉树的中序遍历

94. 二叉树的中序遍历

给定一个二叉树的根节点 root ，返回 它的 中序 遍历 。

示例 1：

输入：root = [1,null,2,3]
输出：[1,3,2]

示例 2：

输入：root = []
输出：[]

示例 3：

输入：root = [1]
输出：[1]

提示：

• 树中节点数目在范围 [0, 100] 内
• -100 <= Node.val <= 100

进阶: 递归算法很简单，你可以通过迭代算法完成吗？

Go代码

/*** Definition for a binary tree node.* type TreeNode struct {*     Val int*     Left *TreeNode*     Right *TreeNode* }*/
func inorderTraversal(root *TreeNode) []int {if root == nil {return []int{}}res := make([]int,0)traversal(root,&res)return res
}func traversal(root *TreeNode,res *[]int)  {if root == nil {return }traversal(root.Left,res)*res = append(*res,root.Val)traversal(root.Right,res)
}