二叉树递归套路总结

之前所有用到二叉树递归套路的时间复杂度都是 $O(N)$，其中 $N$ 是二叉树的节点个数，且都是最优解。

某个节点从左右孩子获取信息，然后整合到该节点，此时的左右孩子已经不需要了，而该节点的父节点也是重复这个过程，整个过程相当于后序遍历，在树上做动态规划，所以叫做树型dp。

这个套路包括两个层次：

1. 思想提醒
   目标如何实现：X 为根节点的二叉树如何实现目标？
   实现手段：向左右树要信息，列举可能性，这个可能性一定是基于从左右树要来的信息（常数时间内可以得到的），加工出来的同等量级的信息也是常数时间的。
   设计信息体，分析可能性，常见的分类是 “与目标 X 有关” 和 “与目标 X 无关”。

2. 模板
   ① 设计 Info 信息体；
   ② process 函数：process 函数一定要返回 Info；遇到空的时候，如果值不好设置就返回空，如果好设置就设置；
   ③默认先得到左树信息，然后得到右树信息；
   ④分析完可能性后，把 X 需要的信息都加工出来，这是高度模板化的。

这个套路可以解决绝大多数的二叉树问题尤其是树型dp问题，本质是利用 递归遍历二叉树 的便利性。

整个流程总结如下：

1）假设以 X 节点为根，假设可以向 X 左树和 X 右树要任何信息

2）在上一步的假设下，讨论以 X 为根节点的树，得到答案的可能性（最重要）

3）列出所有可能性后，确定到底需要向左树和右树要什么样的信息

4）把左树信息和右树信息求全集，就是任何一棵子树都需要返回的信息S

5）递归函数都返回S，每一棵子树都这么要求

6）写代码，在代码中考虑如何把左树的信息和右树信息整合出整棵树的信息