二叉树
遍历
按照顺序规则的不同,遍历方式有以下四种:
- 先序遍历
- 中序遍历
- 后序遍历
- 层次遍历（不重要）
按照实现方式的不同，遍历方式又可以分为以下两种：
- 递归遍历（先、中、后序遍历）
- 迭代遍历（层次遍历）
对树的遍历，就可以看做是对这三个部分的遍历。
- 根结点 -> 左子树 -> 右子树
- 左子树 -> 根结点 -> 右子树
- 左子树 -> 右子树 -> 根结点
上述三个遍历顺序，就分别对应了二叉树的先序遍历、中序遍历和后序遍历规则。
先序遍历
编写一个递归函数之前，大家首先要明确两样东西：
- 递归式
- 递归边界
递归式，它指的是你每一次重复的内容是什么。在这里，我们要做先序遍历，那么每一次重复的其实就是 根结点 -> 左子树 -> 右子树 这个旅行路线。
递归边界，它指的是你什么时候停下来
js
// 所有遍历函数的入参都是树的根结点对象
function preorder(root) {
// 递归边界，root 为空
if(!root) {
return
}
// 输出当前遍历的结点值
console.log('当前遍历的结点值是：', root.val)
// 递归遍历左子树
preorder(root.left)
// 递归遍历右子树
preorder(root.right)
}TIP
d / e 节点退出是因为没有 root，代码中执行了 return, 当执行完 d 和 e 节点时, b 的这个方法要结束了，可以退出，又回到了 root.right 节点，退出是因为函数执行完毕了
当前遍历的结点值是： A
当前遍历的结点值是： B
当前遍历的结点值是： D
当前遍历的结点值是： E
当前遍历的结点值是： C
当前遍历的结点值是： F中序遍历
js
// 所有遍历函数的入参都是树的根结点对象
function inorder(root) {
// 递归边界，root 为空
if(!root) {
return
}
// 递归遍历左子树
inorder(root.left)
// 输出当前遍历的结点值
console.log('当前遍历的结点值是：', root.val)
// 递归遍历右子树
inorder(root.right)
}后序遍历
js
function postorder(root) {
// 递归边界，root 为空
if(!root) {
return
}
// 递归遍历左子树
postorder(root.left)
// 递归遍历右子树
postorder(root.right)
// 输出当前遍历的结点值
console.log('当前遍历的结点值是：', root.val)
}