labuladong的算法秘籍-读书笔记-东哥带你刷二叉树

东哥带你刷二叉树

二叉树解题的思维模式分两类：

1、遍历 通过遍历一遍二叉树得到答案

2、递归 通过定义一个递归函数，通过子问题答案推到原问题的答案

如果单独抽出一个二叉树节点，它需要做什么事情，需要在什么时候（前、中、后序）做？

快速排序是对二叉树的前序遍历

先求分界点、然后对左右两部分排序

归并排序是对二叉树的后序遍历

先对左右部分排序，然后合并

前中后序都是在遍历二叉树

前中后序是遍历二叉树过程中处理每一个节点的三个特殊时间点

前序位置的代码在刚刚进入一个二叉树节点的时候执行

后序位置的代码在将要离开一个二叉树节点的时候执行

中序位置的代码在一个二叉树节点左子树都遍历完，即将开始遍历右子树的时候执行

二叉树的所有问题，就是让你在前中后序位置注入巧妙的代码逻辑，去达到自己的目的，你只需要单独思考每一个节点应该做什么，其他的不用你管，抛给二叉树遍历框架，递归会在所有节点上做相同的操作。

二叉树题目的递归解法可以分两类思路，第一类是遍历一遍二叉树得出答案，第二类是通过分解问题计算出答案，这两类思路分别对应着 回溯算法核心框架 和 动态规划核心框架。

力扣104题 二叉树最大深度

前序位置的代码只能从函数参数中获取父节点传递来的数据，而后序位置的代码不仅可以获取参数数据，还可以获取到子树通过函数返回值传递回来的数据。

一旦你发现题目和子树有关，那大概率要给函数设置合理的定义和返回值，在后序位置写代码了。

力扣543题 二叉树的直径