本文是递归算法系列文的第7篇，依然沿着递归的脉络，介绍了常常运用递归处理问题的一个典型数据结构——二叉树。分析总结了LeetCode中的相关习题在解法上的思路和模板。
本文内容如下：
树的前、中、后序、层次遍历的递归和非递归写法LeetCode上树的问题分类（基本遍历、路径、计数、加和、深宽、构造、BST等）两种遍历为思想的问题（判定、比较结点或子树 以及 路径[ 和 ]、累计）【小结】在解决树的遍历相关问题时，我们是如何使用基本遍历方法，进行递归设计的？由于树的相关问题题目较多，本文介绍第一部分，其余部分后续更新。（又挖了一个坑）
LC144前序
List<Integer> res = new ArrayList<>(); public List<Integer> preorderTraversal(TreeNode root) { if(root == null) return res; res.add(root.val); preorderTraversal(root.left); preorderTraversal(root.right); return res; }LC94中序
List<Integer> res = new ArrayList<>(); public List<Integer> inorderTraversal(TreeNode root) { if(root == null) return res; inorderTraversal(root.left); res.add(root.val); inorderTraversal(root.right); return res; }LC145后序
List<Integer> res = new ArrayList<>(); public List<Integer> postorderTraversal(TreeNode root) { if(root == null) return res; postorderTraversal(root.left); postorderTraversal(root.right); res.add(root.val); return res; }注：前序还有一种写法：这种写法具有结构对称美哦~后序就知道了
根不空时，根入栈当栈非空时： 根出栈，加入res。若右子树非空，右子树入栈若左子树非空，左子树入栈 public List<Integer> preorderTraversal(TreeNode root) { List<Integer> res = new ArrayList<>(); if(root == null) return res; Deque<TreeNode> stack = new ArrayDeque<>(); TreeNode p = root; stack.push(p); //根节点入栈 while(!stack.isEmpty()){ //当根节点不空时，出栈一个根节点，然后加入res中 p = stack.pop(); res.add(p.val); if(p.right != null) //加入右子树入栈 stack.push(p.right); if(p.left != null) //左子树入栈 stack.push(p.left); } return res; }后序遍历使用了一个小技巧：
后序遍历是右 =》左 =》 根， 那么我们可以先按照根 =》左 =》右（前序）进行遍历，然后将得到的结果进行翻转 public List<Integer> postorderTraversal(TreeNode root) { List<Integer> res = new ArrayList<>(); if(root == null) return res; Deque<TreeNode> stack = new ArrayDeque<>(); // Deque<TreeNode> temp_res = new ArrayDeque<>(); TreeNode p = root; stack.push(p); while(!stack.isEmpty()){ p = stack.pop(); res.add(p.val); if(p.left != null) stack.push(p.left); if(p.right != null) stack.push(p.right); } Collections.reverse(res); //将结果翻转，这一步也可以用栈 return res; }以LC102为例：输入二叉树数组，输出层次遍历结果，并且每一层为一个list，整体为二维list
https://leetcode-cn.com/problems/binary-tree-level-order-traversal/
public List<List<Integer>> levelOrder(TreeNode root) { List<List<Integer>> res = new ArrayList<>(); if(root == null) return res; Deque<TreeNode> queue = new ArrayDeque<>(); queue.offer(root); while(!queue.isEmpty()){ List<Integer> item = new ArrayList<>(); for(int i = queue.size() ; i > 0 ; i --){ TreeNode node = queue.poll(); item.add(node.val); if(node.left!= null) queue.offer(node.left); if(node.right!= null) queue.offer(node.right); } res.add(item); } return res; }LC中树标签下的前60来道题经过总结，从问题角度，大概如下包括类别：【标红为本次涉及内容，未标红为后续文章内容】
遍历树进行比较（结点、子树）
深度、路径（和）、计数
（修改）构造相关
根据遍历构造（前中构造，后中构造）前序后继、链表转化AVL（这个与深度关系也大）翻转、修改等构造序列化反序列化二叉搜索树相关（可能会运用BST性质来解题）
明显带有层次遍历的暗示
宽度、锯齿遍历、层平均值、最大值、左右视图、右侧指针顺序（前继后继）
暂且大概将其分为这些类别
其实这样分类也不是太好，一是有些题的从解法层面有多种，二是有些虽然题虽然属于这一类，但是解法更像另一类。。能力有限还请见谅
LC100相同的树
思路：
判断树相同等价于：对两棵树的每一对应节点左如下判断：
若p，q同时为空，则为true若一个空一个非空，则为false若p、q两个非空： p.val 与 q.val 不等，则false若相等，对其左右子树进行上述相同判断（递归），且当左右子树同时满足时，返回true
public boolean isSameTree(TreeNode p, TreeNode q) { if(p == null && q == null) return true; if(p == null || q == null || p.val != q.val) return false; return isSameTree(p.left , q.left) && isSameTree(p.right, q.right); }LC101对称二叉树
1 / \ 2 2 / \ / \ 3 4 4 3思路：按照对称条件，对应节点相等(左子树的左子树与右子树的右子树、左子树的右子树与右子树的左子树)
若根为空直接返回true比较根的左子树和右子树（值是否相等） 左右子树同为null ==> true左右子树只有一个为null，或者都不为null但值不同 ==> false递归对：左子树的左子树与右子树的右子树、左子树的右子树与右子树的左子树 进行考察 public boolean isSymmetric(TreeNode root) { if(root == null) return true; return compare(root.left , root.right); } private boolean compare(TreeNode node1, TreeNode node2){ if(node1 == null && node2 == null) return true; if(node1 == null || node2 == null || node1.val != node2.val) return false; return compare(node1.left , node2.right) && compare(node1.right , node2.left); }LC110平衡二叉树
思路1
平衡二叉树 等价于下面两个条件都满足：
左子树高度与右子树高度差为1左右子树也为平衡二叉树 public boolean isBalanced(TreeNode root){ if (root == null) return true; return Math.abs(depth(root.left) - depth(root.right)) <=1 && isBalanced(root.left) && isBalanced(root.right); } //就是求高度 private int depth(TreeNode node){ if(node == null) return 0; if(node.left == null && node.right == null) return 1; return Math.max(depth(node.left) , depth(node.right)) +1; }思路2：
精妙之处在于用-1表示非平衡，0、1分别表示两棵树（为平衡时）的高度差，大于1也表示非平衡向左递归到最左得到左边结果left （表示的是以所有左子树的判断结果）向右递归到最右得到右边结果right（表示的是以所有右子树的判断结果）返回结果：即考察左右两子树差值是否小于2 public boolean isBalanced(TreeNode root){ if(root == null) return true; return checkBalanced(root) != -1; } private int checkBalanced(TreeNode node){ if(node == null) return 0; int left = checkBalanced(node.left); if(left == -1) return -1; int right = checkBalanced(node.right); if(right == -1) return -1; return Math.abs(left - right) < 2? Math.max(left , right) + 1: -1; }572另一个树的子树
思路：
递归比对s中所有结点与t的根当s某结点值等于t的根的值时，递归比较两子树 boolean flag = false; public boolean isSubtree(TreeNode s, TreeNode t) { if(s == null && t == null) return true; if(s == null || t == null) return false; if(s .val == t.val) flag = verty(s, t); if(flag) return true; //当前节点已经找到了，直接返回truetrue //当前节点没找到，需要递归去左右节点找 flag = isSubtree(s.left , t) || isSubtree(s.right, t); return flag; } //判断以s和t两个节点为根的两个树是否全等 private boolean verty(TreeNode s, TreeNode t) { if(s == null && t == null) return true; if(s == null || t == null) return false; if(s.val != t.val) return false; return verty(s.left , t.left) && verty(s.right , t.right); }LC671二叉树中第二小的节点
思路：通过题意可以看出，该二叉树的最小值即为根，因此我们只需要找到和根值不同的那个最小值即可，它可能在左子树也可能在右子树。
因此，设计递归函数helper(root, root.val)
分别在左子树和右子树中去寻找大于根的值的结点，返回二者中的较小值
public int findSecondMinimumValue(TreeNode root) { if(root == null) return -1; return helper(root, root.val); } private int helper(TreeNode root , int min){ if(root == null) return -1; if(root.val > min) return root.val; //这里表示找到了 int left = helper(root.left , min); int right = helper(root.right , min); if(left == -1) return right; if(right == -1) return left; return Math.min(left , right); }LC104.二叉树的最大深度
思路：该树深度即为左子树和右子树深度大的那个值加1。 对于其左子树和右子树同样如此，因此进行递归求解
public int maxDepth(TreeNode root) { if(root == null) return 0; int left_height = maxDepth(root.left); int right_height = maxDepth(root.right); return Math.max(left_height, right_height)+1; }LC111.二叉树的最小深度
思路：二叉树最小深度即为左子树和右子树中深度小的那个
public int minDepth(TreeNode root) { if(root == null) return 0; if(root.left == null && root.right == null) return 1; //注意此处，当左或右子树边没有时，需要在另一边加1 if(root.left == null) return minDepth(root.right) +1; if(root.right == null) return minDepth(root.left) +1; return Math.min(minDepth(root.left) , minDepth(root.right)) +1; }LC124二叉树中的最大路径和
思路：求从任意一个节点到另一个节点的最大路径。我们需要在递归函数中需要做两件事：
返回从该节点到下方某节点（也有可能就是自身不动）的路径最大值对该节点，比较更新 res 和（当前节点值+左路径最大值 + 右路径最大值） -10 25 （34） / \ / \ 9 20 ==》 9（9） 35 （35） / \ / \ 15 -7 15（15） 0（-7） 对于9，15，-7叶子节点，其返回9,15,0 （负数返回0，表示上面的节点不会来这）对20节点来说，返回其与左孩子节点和35，根节点类似上图中，无括号的表示每个位置处返回的最大往下的路径； 括号中表示此时的最终结果（res） int res = Integer.MIN_VALUE; public int maxPathSum(TreeNode root) { dfs(root); return res; } private int dfs(TreeNode root){ if(root == null) return 0; int left = dfs(root.left); int right = dfs(root.right); res = Math.max(res , left + root.val + right); return Math.max(0 , root.val + Math.max(left,right)); }LC129求根到叶子节点数字之和
思路：在进行递归遍历时，保存一个curr，用于存放目前为止的结果，因此在递归遍历中，对每个结点
int res ; public int sumNumbers(TreeNode root) { if(root == null) return 0; dfs(root , 0); return res; } private void dfs(TreeNode node , int curr){ if(node == null) return; curr += node.val; if(node.left == null && node.right == null ) res += curr; dfs(node.left , curr*10); dfs(node.right , curr*10); }LC112路径总和
思路：判断在树中存在一条和为未指定值的路径，递归遍历，每次将sum减去当前val即可
public boolean hasPathSum(TreeNode root, int sum) { if(root == null) return false; if(sum == root.val && root.left == null && root.right == null) return true; boolean left = false, right = false; //if(root.left != null ) 前面已经对root进行判空 left = hasPathSum(root.left , sum - root.val) ; //if(root.right != null) right = hasPathSum(root.right , sum - root.val); return left || right; }LC113路径之和2
public List<List<Integer>> pathSum(TreeNode root, int sum) { List<List<Integer>> res = new ArrayList<>(); if(root == null) return res; Deque<Integer> item = new ArrayDeque<>(); dfs(root, sum , res ,item); return res; } private void dfs(TreeNode node , int sum , List<List<Integer>> res ,Deque<Integer> item ){ if(node == null ) return; item.add(node.val); if(sum == node.val && node.left == null && node.right == null){ res.add(new ArrayList<Integer>(item)); item.removeLast(); //回溯,返回上一个节点 return; } dfs(node.left , sum - node.val , res , item); dfs(node.right , sum - node.val , res, item); item.removeLast(); //回溯 }LC437路径总和3
思路：该题在111的基础上扩充了两点：
111从根出发，该题是从任意节点出发 针对该问题，我们需要将每个节点视为根进行遍历一次。 111到达叶子，该题可到任意下方节点 结束条件不用再判断是否为叶子 public int pathSum(TreeNode root, int sum) { if(root == null ) return 0; //求以该节点为根的路径个数 int res = findPath(root, sum); //对每个节点，都作为根进行寻找路径 int left = pathSum(root.left , sum); int right = pathSum(root.right , sum); //最后返回：当前节点出发的路径数+左子树所有满足的路径+右子树所有路径 return left + res + right; } //求以这个节点为根的路径个数的具体实现 private int findPath(TreeNode node, int sum){ if(node == null) return 0; int count = sum == node.val ? 1 : 0; //若到达此处时，sum刚好还剩node.val，count计为1 return count + findPath(node.left ,sum - node.val) + findPath(node.right, sum -node.val); }LC257二叉树的所有路径
public List<String> binaryTreePaths(TreeNode root) { List<String> res = new ArrayList<>(); if(root == null) return res; dfs(root, res , new StringBuilder()); return res; } private void dfs(TreeNode root, List<String> res ,StringBuilder stringBuilder){ if(root == null ) return ; if(root.left == null && root.right == null){ res.add(stringBuilder.toString() + root.val); }else{ String temStr = root.val + "->"; stringBuilder.append(temStr); dfs(root.left , res , stringBuilder); dfs(root.right , res ,stringBuilder); //回溯 stringBuilder.delete(stringBuilder.length() - temStr.length(), stringBuilder.length()); } }LC687最长同值路径
思路：此题和124,类似，都是在递归同时要干两件事：
返回的是该节点作为根时树中的最长同值路径比较 int res; public int longestUnivaluePath(TreeNode root) { res = 0; getLength(root); return res; } private int getLength(TreeNode root) { if(root == null) return 0; int left = getLength(root.left);//递归求解左子树的结果 int right = getLength(root.right); int tem_left = 0 , tem_right = 0; if(root.left != null && root.val == root.left.val) tem_left += left+1; //左边结果值为左边递归返回的结果加1 if(root.right != null && root.val == root.right.val) tem_right += right +1; res = Math.max(res , tem_left +tem_right); return Math.max(tem_left,tem_right); }LC404左子树之和
思路：可以中途传值
public int sumOfLeftLeaves(TreeNode root) { if(root == null ) return 0; int sum = 0; if(root.left != null && root.left.left ==null && root.left.right == null) sum += root.left.val; return sum + sumOfLeftLeaves(root.left) + sumOfLeftLeaves(root.right); }LC508出现次数最多的子树元素和
思路：
对每个结点，求其子树和，放到一个HashMap<子树和，次数>， Map<Integer,Integer> hasMap = new HashMap<>(); public int[] findFrequentTreeSum(TreeNode root) { dfs_starNode(root ); //此时hashMap中存放各个顶点的子树和及其出现的次数 //遍历得到出现最多值的次数 int maxCount = 0; for(Map.Entry<Integer, Integer> entry : hashMap.entrySet()) { if(entry.getValue() > maxCount) maxCount = entry.getValue(); } //根据次数，再次遍历，得到和 List<Integer> resList = new ArrayList<>(); for(Map.Entry<Integer, Integer> entry : hashMap.entrySet()) { if(entry.getValue() == maxCount) resList.add(entry.getKey()); } //list => int[] int res[] = new int[resList.size()]; for(int i = 0 ; i < resList.size() ; i++) { res[i] = resList.get(i); } return res; } //从每个点存放 其作为根时子树的和 private void dfs_starNode(TreeNode root) { if(root == null) return ; int val = dfs_getSum(root); // resList.add(val); if(hashMap.containsKey(val)) hashMap.put(val, hashMap.get(val)+1); else hashMap.put(val, 1); dfs_starNode(root.left); dfs_starNode(root.right); } //求和 private int dfs_getSum(TreeNode root) { // System.out.println("+"); if(root == null) return 0; return root.val +dfs_getSum(root.left) +dfs_getSum(root.right); }LC222.完全二叉树的结点个数
思路：
在countNodes递归函数中，做如下事情：
计算当前结点的左子树层数left
计算当前结点的右子树层数right
若left = right ：
则说明就当前结点而言，左子树一定是满的（完全二叉树性质），返回时加上
若left != right
右子树满，返回时加上递归求左子树的结点数
public int countNodes(TreeNode root) { if(root == null) return 0; int left= countLevel(root.left); int right = countLevel(root.right); if(left == right) return countNodes(root.right) + ( 1<<left); //左子树满 else return countNodes(root.left) + (1 << right); //右子树满 } private int countLevel(TreeNode node) { int level = 0; while(node!= null) { level ++; node = node.left ; //完全二叉树左子树具有代表性 } return level; }上面的两类题型（比较判定、路径累计）从本质上来说都是属于遍历性问题的，只不过在遍历过程中，比基本遍历的操作更为麻烦（辅助变量、集合列表） 和/或 逻辑更为复杂（左右子树加和、bool运算、回溯、剪枝） 。
那么，以前序遍历的模板为例，我们可以总结归纳很多相类似问题的解题规律和套路（希望如此）：
（1）基础遍历模板：
public void preorder(TreeNode root) { if(root == null) return； //判空条件不可少，因为下面要取root的左右子树，也可能取val /* 这里每一轮遍历需要做的事情 */ //TODO preorder(root.left); //递归对其左子树做相同的事情 preorder(root.right); //递归对其右子树做相同的事情 }在每一个结点的关键处理步骤中：
/* 这里每一轮遍历需要做的事情 */我们可能用一个变量去累计每个结点的和（已达到我们需要的结果）
也可能会用一个集合去收集，那么这些个集合作为参数在递归过程中传递就好，这一点在前面文章中有详细介绍：
public void dfs(TreeNode root, ArrayList<Integer> item, ... ) { //下面操作类似，每一轮可能会有添加，移除等试探回溯的操作注意到这种返回类型是void，其实我们一般会在外部声明好一些变量（累计和、结果集合等），在遍历过程中对其进行改变，因此这种往往作为一些辅助函数，比如：
//LC671二叉树中第二小的节点 public int findSecondMinimumValue(TreeNode root) { if(root == null) return -1; return helper(root, root.val); } ... //LC127 public List<String> binaryTreePaths(TreeNode root) { List<String> res = new ArrayList<>(); //外部变量，在递归中进行修改 if(root == null) return res; dfs(root, res , new StringBuilder()); //主要进行递归的函数 return res; } ...（2）带返回值的遍历模板：
有时我们会设计递归函数返回我们所需要的结果，比如：
返回 数值 类型：
往往出现在求某些满足条件的结果，累计（深度、个数等）、路径（和）
返回 布尔 类型：
往往出现在对于结点的判断（比较相等、是否满足条件）
数值型遍历模板如下：
public int dfs(TreeNode root) { if(root == null) return 0; int left = dfs(root.left); //递归对root的左子树求取结果 int right = dfs(root.right); //递归对root的右子树求取结果 /* 一些对左右子树的操作、比较、统计等 */ //TODO return 与left和right有关的操作结果 }上面那种也可以看做是一股脑走到叶子结点，然后再逐个返回其结果，然后根据返回的结果进行相应的操作。
例如：返回一棵树中所有结点值的和
private int dfs_getSum(TreeNode root) { if(root == null) return 0; int left = dfs(root.left); int right = dfs(root.right); return root.val +left + right; }例如：LC104求二叉树的最大深度：
public int maxDepth(TreeNode root) { if(root == null) return 0; int left_height = maxDepth(root.left); int right_height = maxDepth(root.right); return Math.max(left_height, right_height)+1; //取左右子树中深的那个，再加1 }判断：检查是否平衡（通过返回值的绝对值小于等于1来判断）：
private int checkBalanced(TreeNode node){ if(node == null) return 0; int left = checkBalanced(node.left); //递归求左子树 if(left == -1) return -1; int right = checkBalanced(node.right); if(right == -1) return -1; //关键：判断每个结点的左右子树的高度差绝对值是否小于2 //若是，则加上自身的高度（返回:子树高度+1） //若否：直接返回-1 return Math.abs(left - right) < 2? Math.max(left , right) + 1: -1; }bool型遍历模板类似，只是在操作中更多的是比较：
public boolean dfs(TreeNode root){ if(root == null) return false; /*这里往往有一些满足结果的结束条件，也有可能有一些剪枝条件*/ //TODO boolean left = false , right = false; left = dfs(root.left); //递归对左子树进行判断 right = dfs(root.right); //递归对右子树进行判断 return 对左右结果left和right进行操作，这里往往就是bool操作 }例如：LC112路径总和
判断棵树中是否有一条从根到叶子的路径，使得其结点val的和等于sum。
public boolean hasPathSum(TreeNode root, int sum) { if(root == null) return false; if(sum == root.val && root.left == null && root.right == null) return true; boolean left = false, right = false; left = hasPathSum(root.left , sum - root.val) ; right = hasPathSum(root.right , sum - root.val); return left || right; }当然，也可以是对两棵树之间进行比较
例如：LC100相同的树
public boolean isSameTree(TreeNode p, TreeNode q) { if(p == null && q == null) return true; if(p == null || q == null || p.val != q.val) return false; return isSameTree(p.left , q.left) && isSameTree(p.right, q.right); //递归对p树的左节点和q数的左节点比较，以及p树的右节点和q树的右节点比较，结果取交集 }以及对称二叉树。
（3）一些复杂或是混合的遍历
这种往往也是由上述两种构成，拆分就好。比如有时我们会进行下列考察：
对树每一个结点，都作为一棵树去递归考察其中结点，如上面[LC572另一个树的子树]和[LC437路径总和3]有时递归中返回的结果值并非是我们想要的，而是在递归函数过程中“其它操作”才是想要的结果。在此类问题中，递归函数往往会做两件事：1、操作a以返回递归结果。2、递归过程中进行一些另外的操作b，操作b与递归结果相结合才能得到该问题结果。。有点绕，参考上面[LC124二叉树中的最大路径和]的解法。本文介绍了二叉树问题中以递归遍历为主的习题以及解法思路。重点剖析了相关遍历模板类型和应用。有关递归设计思路以及其他应用可看如下文章：
[算法系列] 搞懂递归, 看这篇就够了 !! 递归设计思路 + 经典例题层层递进[算法系列] 递归应用: 快速排序+归并排序算法及其核心思想与拓展 … 附赠 堆排序算法[算法系列] 深入递归本质+经典例题解析——如何逐步生成, 以此类推,步步为营[算法系列]搞懂DFS(1)——经典例题(数独游戏, 部分和, 水洼数目)图文详解[算法系列]搞懂DFS(2)——模式套路+经典例题详解（n皇后问题，素数环问题）