二叉树

每次写递归，都按照这三要素来写，可以保证大家写出正确的递归算法！

1. 确定递归函数的参数和返回值： 确定哪些参数是递归的过程中需要处理的，那么就在递归函数里加上这个参数， 并且还要明确每次递归的返回值是什么进而确定递归函数的返回类型。
2. 确定终止条件： 写完了递归算法, 运行的时候，经常会遇到栈溢出的错误，就是没写终止条件或者终止条件写的不对，操作系统也是用一个栈的结构来保存每一层递归的信息，如果递归没有终止，操作系统的内存栈必然就会溢出。
3. 确定单层递归的逻辑： 确定每一层递归需要处理的信息。在这里也就会重复调用自己来实现递归的过程。

递归函数什么时候需要返回值？什么时候不需要返回值？这里总结如下三点：

• 如果需要搜索整棵二叉树且不用处理递归返回值，递归函数就不要返回值。（这种情况就是本文下半部分介绍的113. 路径总和 II）
• 如果需要搜索整棵二叉树且需要处理递归返回值，递归函数就需要返回值。 （这种情况我们在236. 二叉树的最近公共祖先中介绍）
• 如果要搜索其中一条符合条件的路径，那么递归一定需要返回值，因为遇到符合条件的路径了就要及时返回。112. 路径总和

题目	难度	备注	关联
144.二叉树的前序遍历	简单			可以再刷
94.二叉树的中序遍历	简单			可以再刷
145.二叉树的后序遍历	简单			可以再刷
102. 二叉树的层序遍历	中等			可以再刷
107. 二叉树的层序遍历 II	中等
199. 二叉树的右视图	中等	这个解法可以的		了解 dfs
637. 二叉树的层平均值	简单			了解 dfs
429. N 叉树的层序遍历	中等
515. 在每个树行中找最大值	中等			了解 dfs
116. 填充每个节点的下一个右侧节点指针	中等			O(1) 空间复杂度
117. 填充每个节点的下一个右侧节点指针 II	中等	这个 O(1) 的解法		O(1) 空间复杂度
104. 二叉树的最大深度	简单
111. 二叉树的最小深度	简单			了解 dfs，可以再刷
226. 翻转二叉树	简单
101. 对称二叉树	简单			可以再刷
559. N 叉树的最大深度	简单
222. 完全二叉树的节点个数	简单	使用完全二叉树的性质 位运算		可以再刷
110. 平衡二叉树	简单			可以再刷
257. 二叉树的所有路径	简单	层次遍历的解法比较新颖		可以再刷
404. 左叶子之和	简单
513. 找树左下角的值	简单	深度遍历的思路有点意思		可以再刷
112. 路径总和	简单	层次遍历的双队列可以		可以再刷
113. 路径总和 II	中等	回溯		可以再刷
654. 最大二叉树	中等	构造二叉树		可以再刷
617. 合并二叉树	简单	构造二叉树		可以再刷
106. 从中序与后序遍历序列构造二叉树	中等	构造二叉树		可以再刷
105. 从前序与中序遍历序列构造二叉树	中等	构造二叉树		可以再刷
700. 二叉搜索树中的搜索	简单
98. 验证二叉搜索树	中等			可以再刷
530. 二叉搜索树的最小绝对差	简单	二叉搜索树的中序遍历 节点的值是递增的
501. 二叉搜索树中的众数	简单			可以再刷