Leetcode中的递归的问题总是很头疼，特别对于二叉树问题，因为二叉树是左右子树的形式，天生就具有递归性。在这篇文章中，系统总结一套解决递归问题的模版思路与解法，以后使用这个思路可以秒解很多二叉树的递归问题。
递归解题三部曲何为递归？程序反复调用自身即是递归。
我自己在刚开始解决递归问题的时候，总是会去纠结这一层函数做了什么，它调用自身后的下一层函数又做了什么…然后就会觉得实现一个递归解法十分复杂，根本就无从下手。
相信很多初学者和我一样，这是一个思维误区，一定要走出来。既然递归是一个反复调用自身的过程，这就说明它每一级的功能都是一样的，因此我们只需要关注一级递归的解决过程即可。
记住：千万不要去纠结每一级调用和返回的细节。
如上图所示，我们需要关心的主要是以下三点：
1）整个递归的终止条件。
2）一级递归需要做什么？
3）应该返回给上一级的返回值是什么？
因此，也就有了我们解Binary Tree递归题的三部曲：
1）找整个递归的终止条件：递归应该在什么时候结束？
2）找返回值：应该给上一级返回什么信息？
3）本级递归应该做什么：在这一级递归中，应该完成什么任务？
一定要理解这3步，这就是以后秒杀递归算法题的依据和思路。
注意左右子树的递归，当前级就是右侧这种结构：
最后得到的代码如下：
class Solution { public int maxDepth(TreeNode root) { return root == null ? 0 : Math.max(maxDepth(root.left), maxDepth(root.right)) + 1; }}
https://leetcode.com/problems/count-complete-tree-nodes/
这道题按照上面的递归三部曲来做，不考虑是一颗完全二叉树。很简单可以得到一个初步的解答：
public int countNodes(TreeNode root) { // o(n)时间复杂度 if (root == null) return 0; int left = countNodes(root.left); int right = countNodes(root.right); return left + right + 1;}如果考虑到是一颗完全二叉树，而我们知道，满二叉树的节点数和高度的计算公式是：
N = 2 ^ h – 1 (h 从1开始，根节点是1.)
所以对于一颗完全二叉树，如果它的一个节点的左子树的高度 == 右子树的高度，那么就可以使用该公式直接计算节点数量，如果不相等，才使用上面的方法，递归遍历每一个节点，将数量增加。这样得到的代码如下：
public int countNodes(TreeNode root) { int left_h = 0, right_h = 0; TreeNode left = root, right = root; while(left != null) { left_h++; left = left.left; } while(right != null) { right_h++; right = right.right; } if (right_h == left_h) { return (int) Math.pow(2, left_h) - 1; // 满二叉树的节点个数是2 ^h - 1(h为高度) } return countNodes(root.left) + countNodes(root.right) + 1; }对于这个算法的复杂度，leetcode评论中有人给出：
Since I halve the tree in every recursive step, I have O(log(n)) steps. Finding a height costs O(log(n)). So overall O(log(n)^2).
https://leetcode.com/problems/flatten-binary-tree-to-linked-list/
这道题，我们也是采用上面的三部递归，在构思的时候，考虑到divid and conquer的思想，当我们递归调用root的left和right后，可以认为left和right都已经flatten到位了，所以我们要做的，是在conquer的时候将root， 已经flatten的left和right树连接起来。具体的实现看代码：
public void flatten(TreeNode root) { if (root == null) return; flatten(root.left); flatten(root.right); // 先对左右子树调用flatten()函数，则表示此时左、右子树已经做好了flatten操作 // 将root, root.left, root.right 连成一个link list /* 1 l / r (2->3>4) (5->6) */ TreeNode right = root.right; TreeNode left = root.left; if (right == null) { // 右子树为空，直接将root连上左子树 root.right = left; root.left = null; return; } if (left == null) { // 左子树为空，直接返回 return; } while(left.right != null) { // 左右子树都不为空，找到left的最后一个节点，将其和right子树连起来 left = left.right; } left.right = right; root.right = root.left; root.left = null; }
该文主要参考了该篇博文：https://www.jianshu.com/p/1395fae8a1ae
具体的题目可以查看leetcode的二叉树tag： https://leetcode.com/tag/binary-tree/
解决的题目见https://leetcode.com/list/ 的Binary Tree(BFS/DFS)的收藏页。