二叉树的递归算法模板(二叉树递归算法代码)
定义篇：
这里主要讲解一下二叉树的基本知识，方便大家0基础入学
引入：
二叉树是n个结点的有限集合，n=0叫空树。
1）有且只有一个结点的叫树的根结点
2）如果n>1，其余结点被分为2个互不相交的子集，叫做左右子树，且左右子树都是二叉树。
由此可称：二叉树定义是递归的
二叉树的五种形态：
神奇的二叉树算法
前中后序遍历：
递归两个要素
1.递归边界 2.递归的逻辑——递归"公式"
public ListNode reverseList(参数0) { if (终止条件) return; 逻辑处理（可能有，也可能没有，具体问题具体分析） //递归调用 ListNode reverse = reverseList(参数1); 逻辑处理（可能有，也可能没有，具体问题具体分析） } 复制代码中序遍历：
中序是 左根右的遍历，即先访问左结点，再根结点，最后右结点
递归终止条件： if(当前结点==null){return;} 递归调用： digui(node.left) 处理当前node digui(node.right)
代码模板如下：
public void digui(TreeNode node){ if(node==null){ return; } digui(node.left); System.out.println(node.val); digui(node.right); } 复制代码eg: 给定一个二叉树的根节点 root ，返回 它的 中序 遍历 。
示例 1：
输入：root = [1,null,2,3] 输出：[1,3,2]
public void digui2(TreeNode node,List<Integer> list){ if(node==null){ return; } digui2(node.left,list); list.add(node.val); digui2(node.right,list); } 复制代码前序后序遍历
前序遍历：根左右 后序遍历：左根右
同上一个中序遍历类似：
前序递归调用： 处理当前node； digui(node.left)； digui(node.right)
后序递归调用 digui(node.left)； digui(node.right) 处理当前node；
通过前序中序，构造二叉树
当知道一个数前序中序遍历了，怎么构造这个二叉树？
我们已知：
前序遍历：根-》左-》右
中序遍历：左-》根-》右
后续遍历：左-》右-》根
那么这样我们可以通过前序确定整个树的根，即前序第一个数，然后在中序里面把其分成左右子树，再次通过前序对应子树排序，找到左右子树根，再次划分等。我们可以调用递归，递归结束条件就是中序长度为0，循环条件是，调用本方法，保证输出根，划分子树。
public TreeNode getTree(List<Integer> pre,List<Integer> ino){ if(ino.size()==0){ return null; } int rootVal=pre.remove(0); int mid=ino.indexOf(rootVal); //把中序，按照根划分左右子树 root.left=getTree(pre,ino.subList(0,mid)); root.right=getTree(pre,ino.subList(mid+1,ino.size())); return root; } 复制代码层次遍历：
层次遍历也需要递归： 所以递归终止条件： if(root==0){return ;}
如何统计下一层？
我们通过设置一个level来标识层数，List<List《Integer>> list来存储树，如果level>=list.size()，说明到了下一层。开始进行下一层遍历。
public void levelHelper(List<List<Integer>> list, TreeNode root, int level) { //边界条件判断 if (root == null) return; //level表示的是层数，如果level >= list.size()，说明到下一层了，所以 //要先把下一层的list初始化，防止下面add的时候出现空指针异常 if (level >= list.size()) { list.add(new ArrayList<>()); } //level表示的是第几层，这里访问到第几层，我们就把数据加入到第几层 list.get(level).add(root.val); //当前节点访问完之后，再使用递归的方式分别访问当前节点的左右子节点 levelHelper(list, root.left, level + 1); levelHelper(list, root.right, level + 1); } 复制代码深度遍历
给定一个二叉树，找出其最大深度。
二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。
说明: 叶子节点是指没有子节点的节点。
示例： 给定二叉树 [3,9,20,null,null,15,7]
仍然使用递归：
如果root=null返回0，否则以左或者右结点作为根节点，再次使用本函数。里面继续递归调用
class Solution { public int maxDepth(TreeNode root) { if(root==null){ return 0; }else{ return Math.max(maxDepth(root.left), maxDepth(root.right))+1; } } }
作者：My2538772270
链接：https://juejin.cn/post/7169120529960402958