递归套路

二叉树的递归套路三步走：
目标以X节点为头节点完成指定功能，需要向左右孩子要哪些信息。注意，这些信息必须是在常数时间内可以得到的。

  1. 设计信息体，
  2. 分析可能性（重要，通常分析这个结果和X有关时，和X无关时两大类可能性，然后再基于这两类可能性进行细分）
  3. 书写递归过程

递归方法一个节点只会经过三次，树的递归套路。树型DP问题。

  1. 假设以X节点为头节点，假设可以向X左子树和X右子树要任何信息
  2. 在上一步的假设下，讨论以X为头节点的树，得到目标答案的几种可能性
  3. 列出所有的可能后，确定到底向左树和右树要什么样的信息
  4. 把左树信息和右树信息求全集作为信息体Info，也就是任何一棵子树都需要返回的Info
  5. 递归函数返回Info，每棵子树都这么要求
  6. 写代码，在代码中考虑如何把左树的信息和右树的信息整合出整棵树的信息

递归套路的时间复杂度是O(N),N表示的是节点的个数。

从头节点开始，往下要信息，eg：Info中，向子树要三个信息，对于叶子节点，左边是空，要来三个信息，左边是空要来三个信息，左边得到的三个信息和右边得到的三个信息整合成当前节点的三个信息，然后向上传，依次同理。整个递归套路过程就相当于二叉树的后续遍历，在树上做动态规划，所以叫树形DP。

因为递归方法，一个节点只会经过三次，所以递归套路的本质就相当于遍历了一个树，一个递归序的遍历，每个节点遍历了三次，时间复杂度就是O(N)。