![](https://csdnimg.cn/release/download_crawler_static/88001700/bg1.jpg)
关于⼆叉树遍历问题的⼀些总结(持续更新~~~~2021.5.19)
⼀、⼆叉树的重要性
很多经典算法如 回溯、⼴度优先遍历、分治、动态规划等通常需要转化为树的问题,⽽树的题⽬难免涉及到递归的问题,因此掌握树的三
种遍历框架是必须的。
先序遍历:根,左,右
中序遍历:左,根,右
后序遍历:左,右,根
可以看到三种遍历的命名主要看根遍历的顺序,左右的先后位置不变。
下⾯直接贴上遍历的框架代码:
/*
⼆叉树遍历框架
*/
void traverse(TreeNode root) {
//
前序遍历
traverse(root.left)
//
中序遍历
traverse(root.right)
//
后序遍历
}
从上⾯的代码不难看出树的三种遍历⽅式其实只是改变了当前节点记录函数的位置,
刚开始学习递归算法的时候很难想明⽩⾥⾯的过程,其实理解遍历⽅式的话不需要对整棵树进⾏模拟,对他的整体逻辑理解或者找⼀个
最简单的⼆叉树特例理解就好了,中间的过程就是因为很难⽤详细⽂字表征才⽤递归的。我们可以取后续遍历来分析,假设遍历的是⼀个最
简单的两层⼆叉树。每次在函数要结束退出时才开始记录当前结点值。可以想象,因为左右结点的遍历函数在当前结点返回函数代码之前,
他们退出函数时⼀定记录了了root->left.val 和 root->right.val,然后才论⽂记录 root->val,这样就实现了中序遍历。
进⼀步地,当层数变多时,由于左⼦树遍历⼀直在挖深度,所以会实现复杂的递归过程~~意会即可。
⼆、写递归算法的秘诀
写递归算法的关键是要明确函数的「定义」是什么,然后相信这个定义,利⽤这个定义推导最终结果,绝不要试图跳⼊递归。 怎么理解上
⾯的话呢?可以看下下⾯的程序,定义:要求我们返回树的结点个数。
```cpp
//
定义:
count(root)
返回以
root
为根的树有多少节点
int count(TreeNode root) {
// base case
if (root == null) return 0;
//
⾃⼰加上⼦树的节点数就是整棵树的节点数
return 1 + count(root.left) + count(root.right);
}
这个问题⾮常简单,⼤家应该都会写这段代码,root本⾝就是⼀个节点,加上左右⼦树的节点数就是以root为根的树的节点总数。
写树相关的算法,简单说就是,先搞清楚当前root节点该做什么,然后根据函数定义递归调⽤⼦节点,递归调⽤会让孩⼦节点做相同的
事情。
上⾯的代码我们⾸先就是在最⼤或者说最开始框架下,需要返回的是节点总数(当前root该做什么),所以我需要计算当前结点个数+左
⼦树节点个数+右⼦树节点个数即可。问题来了,左右⼦树节点个数怎么算?只要你在最⼤框架下待定的计算项和当前的计算过程相同,递
归就完事了,因为你整棵树的节点计算框架已经出来了,左右⼦树也是树,调⽤本⾝即可。
三、算法实践
Leetcode226. 翻转⼆叉树
Leetcode116. 填充⼆叉树节点的右侧指针
Leecode 117. 填充每个节点的下⼀个右侧节点指针 II
Leecode 654. 最⼤的⼆叉树
Leecode 105. 从前序与中序遍历序列构造⼆叉树
Leecode 106. 从中序与后序遍历序列构造⼆叉树