Study NoteAppearance
二叉树的递归遍历
递归 对于很多同学，包括我，都是 “脑子一看，会了；但是上手写就发现不是那么回事儿”
这主要是对于递归的思维没有成体系，没有方法论。
帮助小伙伴，和我一起，掌握递归，掌握二叉树！
递归三要素
确定递归函数的参数和返回值： 确定哪些参数是递归的过程中需要处理的，那么就在递归函数里加上这个参数， 并且还要明确每次递归的返回值是什么进而确定递归函数的返回类型。
确定终止条件： 写完了递归算法, 运行的时候，经常会遇到栈溢出的错误，就是没写终止条件或者终止条件写的不对，操作系统也是用一个栈的结构来保存每一层递归的信息，如果递归没有终止，操作系统的内存栈必然就会溢出。
确定单层递归的逻辑： 确定每一层递归需要处理的信息。在这里也就会重复调用自己来实现递归的过程。
开始刷题
二叉树的前序遍历
题目：144.二叉树的前序遍历
前序遍历的口诀：根、左、右
这好像还是大学老师教的，没想到我还记得！
我这里只给出 js 的题解哈～
根据口诀，我们先遍历根节点，其次是左，接着是右。
接下来来找三要素：
我们的终止条件，就是节点遍历完，最终指向了 null，代表结束遍历。
递归函数的参数，就是我们的树🌲。
单层递归，就是口诀，根，然后左，然后右。
上题解：
js
/**
* @param {TreeNode} root
* @return {number[]}
*/
var preorderTraversal = function(root) {
// 存储返回结果
const arr = []
const dfs = (root) => {
// 如果树为空直接返回
if(root === null) return
if(root.val !== null){
// 根
arr.push(root.val)
// 左
dfs(root.left)
// 右
dfs(root.right)
}
}
dfs(root)
return arr
};
二叉树的后序遍历
题目：145.二叉树的后序遍历
后序遍历的口诀：左、右、根
了解前序遍历后，这个应该很简单了，我们直接上代码：
js
/**
* @param {TreeNode} root
* @return {number[]}
*/
var postorderTraversal = function(root) {
const arr = []
const dfs = (root) => {
if(root === null) return
if(root.val !== null) {
dfs(root.left)
dfs(root.right)
arr.push(root.val)
}
}
dfs(root)
return arr
};
二叉树的中序遍历
题目：94.二叉树的中序遍历
后序遍历的口诀：左、根、右、
理解上述两个遍历后，最后这个应该手到擒来了吧，直接上代码：
js
/**
* @param {TreeNode} root
* @return {number[]}
*/
var inorderTraversal = function(root) {
const res = []
const dfs = (root) => {
if(!root){
return
}
dfs(root.left)
res.push(root.val)
dfs(root.right)
}
dfs(root)
return res
};
至此，我们二叉树递归遍历就刷完了！
你对递归和二叉树，有更深的了解或印象了吗？
接下来我们继续加油吧~