二叉树的遍历

二叉树各种遍历的递归模版

树这种数据结构是非常适合使用递归算法的，因为本身的自身相似性非常强。 我们先以二叉树的前序遍历为例（https://leetcode-cn.com/problems/binary-tree-preorder-traversal/submissions/），前序遍历的顺序为“根左右” 首先定义二叉树的结构： public class TreeNode { int val; TreeNode left; TreeNode right; TreeNode(int x) { val = x; } }

确定输入输出： input: TreeNode root output:前序遍历输出的ArrayList 常规递归模版：

public void helper() { if(递归终止条件) return; 处理当前层 进行递归操作 }

结合前序遍历和输入输出的要求：

public void helper(List<Integer> res , TreeNode node) { if(终止条件) return; //前序遍历，先将当前根节点添加进res，再进入递归添加左子节点和右子节点 res.add(node.val); helper(res,node.left); helper(res,node.right); }

接下来要解决的就是递归终止条件，实际上非常容易想到，当当前节点为空，递归结束

class Solution { //完整代码 public List<Integer> preorderTraversal(TreeNode root) { List<Integer> res = new ArrayList<>(); helper(res,root); return res; } public void helper(List<Integer> res , TreeNode node) { if (node == null) { return; } res.add(node.val); helper(res , node.left); helper(res , node.right); } }

以上就是前序遍历的递归解法，实际上中序遍历与后序遍历只需要在以上的代码中更改节点添加顺序即可（为了简洁我只给出修改的部分）：

//中序遍历(左根右） helper(res , node.left); res.add(node.val); helper(res , node.right); //后序遍历（左右根） helper(res , node.left); helper(res , node.right); res.add(node.val);

二叉树的层序遍历递归解法

https://leetcode-cn.com/problems/binary-tree-level-order-traversal/ 相较于前面的三种遍历，层序遍历的区别在于需要记录“层次” 同样我们使用相同的递归模版： public void helper() { if (递归终止条件) return; 处理当前层 进入递归 }

再根据本题的特点对模版进行填充，我们需要的变量有： input: 根节点（当前节点） output:二维List 记录层次的变量int level

public void helper(TreeNode node , int level , List<List<Integer>> res) { if (node == null) return;//二叉树遍历的常规终止条件 //处理当前层，我们利用res的size来与level进行比对，确定当前层的操作 //res的初始size为0，所以我们设置初始level也为0，当size与level相同时我们创建新的子项 if (res.size() == level) { res.add(new ArrayList<>()); } //当前层的操作就是将当前节点的值添加进对应层次的res子项中 res.get(level).add(node.val); //处理完当前层进入递归 helper(node.left , level + 1 , res); helper(node.right , level + 1 , res); }

递归解法来解二叉树遍历的相关题目是非常简单的，并且相似性非常高，很容易掌握，下一篇的非递归解法才是重头戏。