本文为博客：东哥带你刷二叉树（纲领篇） | labuladong 的算法笔记的笔记
前言
将二叉树的思想传递至动态规划，回溯算法，分治算法，图论算法！
对于二叉树的每一个结点，我们需要思考的是：如果单独抽出一个二叉树节点，它需要做什么事情？需要在什么时候（前/中/后序位置）做？
二叉树的重要性
拿快速排序和归并排序举例子
- 快速排序：二叉树的前序遍历（先确定p，再确定p的左面、p的右面）
- 归并排序：二叉树的后序遍历（确定左面数组、右面数组，对两部分数组进行合并）
只要涉及递归，都可以抽象成二叉树的问题 （学习完二叉树将继续更新动规，回溯等算法，我们先理解好二叉树的思想）
深入理解前中后序
再推一遍：东哥带你刷二叉树（纲领篇） | labuladong 的算法笔记，写的真的好orz
哈哈，反正我是中枪了~
下面分别给出二叉树、数组、链表遍历的框架，可以思考一下有哪些共同点：
单链表、数组可以递归访问，二叉树这种结构无非就是二叉链表 ，只是无法写成迭代遍历。
所谓前序位置，就是刚进入一个节点（元素）的时候，后序位置就是即将离开一个节点（元素）的时候（这句话非常重要，先从数组、链表的角度想）
举个例子，倒序打印链表元素，你会怎么写代码？用上述第三块代码，我们可以在后续位置添加print语句，即可！正序打印在前序位置添加语句即可。二叉树也是一样，二叉树具有前序位置，中序位置，后序位置，前中后序是遍历二叉树过程中处理每一个节点的三个特殊时间点（这句话堪称我一绝哈哈哈，请反复思考orz）
！！！标重点
前序位置的代码在刚刚进入一个二叉树节点的时候执行；
后序位置的代码在将要离开一个二叉树节点的时候执行；
中序位置的代码在一个二叉树节点左子树都遍历完，即将开始遍历右子树的时候执行。
这意味着什么？这意味着你只需要在这个框架上，往前序位置/中序/后序填你想要的代码就可以；这意味着你只需要考虑一个结点就可以（考虑刚刚进入这个节点该做什么，遍历完左子树需要做什么，离开这个节点需要做什么），再回头看二叉树，是不是清晰了很多。再补东哥一句话：你可以发现每个节点都有「唯一」属于自己的前中后序位置。
现在请小朋友回前言再看最后一句话，深思ing
两种解题思路
二叉树题目的递归解法可以分两类思路，第一类是遍历一遍二叉树得出答案，第二类是通过分解问题计算出答案，这两类思路分别对应着 回溯算法核心框架 和 动态规划核心框架。
回溯算法核心框架：没有返回值，靠更新外部变量来计算结果
动态规划核心框架：有返回值，返回值是子问题的计算结果
104. 二叉树的最大深度 - 力扣（LeetCode）再来看这道题，我们用两种写法来写一遍，并且解释为什么代码放在前序/中序/后序位置？
我们先来写回溯算法：
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
void traverse(TreeNode* root,int& depth,int& res){
if(root==nullptr){
return;
}
//前序位置
depth++;
if(depth>res){res=depth;cout<<res<<endl;}
traverse(root->left,depth,res);
//中序位置
traverse(root->right,depth,res);
//后序位置
depth--;
}
class Solution {
public:
int depth=0;
int res=0;
int maxDepth(TreeNode* root) {
traverse(root,depth,res);
return res;
}
};干饭去了，朋友们~
