二叉树的遍历（leetcode 第144、145、94、102题）
一、递归方法论（采用三部曲的步骤）
-
确定递归函数的返回值与参数：确定哪些参数在递归的过程中需要进行处理，那么就在递归的函数里面加上这个参数。同时明确每次递归的返回值是什么，从而根据每次递归的返回值来确定递归函数的返回值。 -
确定递归的终止条件：在写递归的时候经常会遇到栈溢出的错误，这就是因为递归的终止条件写的不对。对于二叉树里面的递归的终止条件，一般来说我们都是对整个二叉树进行遍历或者对二叉树某一条边进行遍历，因此我们不难发现， 递归的终止条件一般都是递归到叶子节点或者递归到空节点（当然有其它情况）。 -
确定单层递归的逻辑：简单来说就是逻辑上的重复的内容。在这里面有几个小的技巧，首先我们可以通过二叉树的三种遍历方式确定我们解题时到底利用的是哪种遍历方式，然后对中间节点进行每次的递归逻辑；另外，递归的的时候我们可以不用考虑的那么复杂，只要知道 每次递归的时候都得到了你想要得到的内容即可（后续的题目会有所体现）。
二、 leetcode 第144题前序遍历，第145题中序遍历，第94题后续遍历
//第144题前序遍历
/*
思路：首先我们对于这道题进行思考，我们需要采用前序遍历的方式对二叉树进行遍历。那么我们自己是如何处理这个问题的呢？是不是首先从根节点出发，然后直接输出根节点；再判断根节点是否有左右子节点，如果有左子节点是不是先将左子节点输出；如果不含左子节点，是不是将右子节点输出；如果都不含，是不是说明到达了叶子节点的位置，直接返回了。后续所有的节点的逻辑是不是都和根节点的逻辑一样？也就是说对于每一个节点我们都采用的同样的逻辑进行操作，这里就可以采用递归进行实现了。
*/
class Solution {
/*
下面进行递归三部曲的操作：
1.确定递归的参数与返回值。
递归的参数：我们需要进行每次操作的参数是什么？是不是每个节点以及节点的输出值？所以我们这里是不是需要一个节点参数，一个列表用来存储每次的节点的值。
递归的返回值：这里我们每次处理完一个节点需要传回什么参数吗？不需要吧。我们每次的操作不就是将节点的值放到列表中就完事了，因此不需要返回值吧。
private void preorder(TreeNode root, List<Integer> result)
2.确定递归的终止条件。
我们刚刚在思路分析的过程中是不是已经发现了，当遍历到叶子节点下一个节点的时候是不是就可以返回了？那就是当root节点走到空节点的位置时，就返回了吧。
if(root == null) return;
3.确定每层的递归逻辑。
首先先序遍历是采用中左右的遍历方式吧，我们每次处理的都是对中节点进行处理，我们只要将中节点放入列表当中，然后再对左右进行递归即可吧。
result.add(root.val);//中节点，将值放入列表当中
preorder(root.left);//左节点递归，这次递归得到了你想要的内容，将左子节点放入了列表
preorder(root.right);//右节点递归，将右子节点放入了列表
*/
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> result = new ArrayList<Integer>();
preOrder(root, result);
return result;
}
private void preOrder(TreeNode root, List<Integer> result) {
if (root == null) {
return;
}
result.add(root.val); //中
preOrder(root.left, result); //左
preOrder(root.right, result); //右
}
}
//同理，第145题中序遍历
class Solution {
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> res = new ArrayList<>();
inorder(root, res);
return res;
}
private void infixOrder(TreeNode root, List<Integer> list) {
if (root == null) {
return;
}
infixOrder(root.left, list); //左
list.add(root.val); //中
infixOrder(root.right, list); //右
}
}
//同理，第94题后续遍历
class Solution {
public List<Integer> postorderTraversal(TreeNode root) {
List<Integer> res = new ArrayList<>();
postorder(root, res);
return res;
}
private void postOrder(TreeNode root, List<Integer> list) {
if (root == null) {
return;
}
postOrder(root.left, list); //左
postOrder(root.right, list); //右
list.add(root.val); //中
}
}
三、二叉树前中后序遍历的迭代实现
-
-
前序遍历的迭代实现
/*
思路分析：首先我们得在自己的脑子里面非常清楚到底前序遍历是如何遍历的。这里我们可以将自己想像成为电脑，每次进行的操作都只能是电脑能进行的操作。
对于一个二叉树前序遍历，我们首先将根节点输出（对上电脑是不是先将根节点入栈，然后再出栈），很多人会觉得是多此一举。但是我们不仅仅是将根节点入栈吧，同时是不是还需要对根节点的左右子节点进行判断？是不是得使用一个cur节点进行遍历，cur节点的遍历是不是可以直接将栈pop出的值赋给他。如果不经过push和pop的过程是不是就无法更新cur节点。
接下来是不是得到了root的值，下面是不是得输出左子节点了？很多人就直接将左子节点push进去然后pop出来，但是这样是不是存在问题，你后续将左子节点全部pop完之后，栈为空了，右子节点咋办？这里我们是不是先得将右子节点入栈，然后再将左子节点入栈，然后再将左子节点pop出来吧？然后此时的cur是不是指向了左子节点，我们继续判断cur是否存在左右子节点吧，继续将右子节点先入栈，然后再左子节点；这样持续下去。
当我们cur指向的节点为右子节点的时候，是不是继续pop一次？这样是不是就回溯到了上一个右子节点的位置了？
*/
class Solution {
public List<Integer> preorderTraversal(TreeNode root){
//首先定义一个栈用来遍历二叉树，一个存储结果的列表
List<Integer> result = new ArrayList<>();
if(root == null){
return result;
}
Deque<TreeNode> stack = new ArrayDeque<>();
//首先将根节点入栈
stack.push(root);
//循环截至的条件为栈为空
while(!stack.isEmpty()){
//首先定义一个遍历的节点，将节点的值添加到result中
TreeNode cur = stack.pop();
result.add(cur.val);
//先将当前节点的右子节点入栈
if(cur.right != null){
stack.push(cur.right);
}
//再将左子节点入栈
if(cur.left != null){
stack.push(cur.left);
}
}
return result;
}
}
//对照代码画一画图就非常清晰了 -
中序遍历的迭代实现
/*
思路分析：刚刚看完上面的前序遍历的话是不是觉得也就如此？但是的话你试试采用上述的前序遍历的方式来实现中序遍历，你会发现完全行不通，两种遍历方式的写法没有很强的共同性。下面我们还是先理清思路。
首先，我们是不是得找到最左边节点的位置，同时得保留一路遍历过来的所有的节点，因为我们还需要回溯到中间节点和右子节点吧。
找到第一个左边的节点（要么为左子节点，要么该节点有右子节点），是不是直接进行pop，然后存储到列表当中；此时我们cur是不是得指向这个节点的右子节点的位置，如果此时cur不为空，又得找到该节点的为根的树的最左边的节点吧；如果右子节点为空，说明找到的是左叶子节点吧，此时继续pop出上一个节点。重复上诉的过程。
*/
class Solution {
public List<Integer> inorderTraversal(TreeNode root){
//首先定义一个存储结果的列表，一个遍历的栈，一个遍历用的节点
List<Integer> result = new ArrayList<>();
if(root == null){
return result;
}
TreeNode cur = root;
Deque<TreeNode> stack = new ArrayDeque<>()；
//循环终止的条件
while(cur == null && !stack.isEmpty()){
//将以以cur为根节点的二叉树的最左边的边界进行入栈
if(cur != null){
stack.push(cur);
cur = cur.left;
}else{ //如果cur.left为空了，说明到了最左边的节点的位置
cur = stack.pop(); //返回该值
result.add(cur.val);
//判断是左叶子节点还是有右子树，有点话继续进if里面
//如果是叶子节点，继续将上一个节点给输出
cur = cur.right;
}
}
return result;
}
} -
后续遍历的迭代实现
/*
思路分析：这里的话又和中序遍历的思路不太一样了。后续遍历的话是先输出左，再右，再中。如果我们按照它本身的方式进行实现的话会发现非常的复杂，因此得换个思路了。
既然它是左右中的实现形式，我们将其反过来就是中右左，你会发现这个中右左是不是和前序遍历的中左右非常的相似，我们只要将左右子节点push进栈的顺序反一下即可；这样我们就可以得到中右左的遍历结果，我们再对这个结果进行反转就得到了后续遍历实现。
*/
class Solution {
public List<Integer> postorderTraversal(TreeNode root){
List<Integer> result = new ArrayList<>();
if(root == null){
return result;
}
Deque<TreeNode> stack = new ArrayDeque<>();
stack.push(root);
while(!stack.isEmpty){
//这里的添加顺序与前序遍历的顺序相反
TreeNode cur = stack.pop();
result.add(cur.val);
if(cur.left != null){
stack.push(cur.left);
}
if(cur.right != null){
stack.push(cur.right);
}
}
//调用reverse方法进行翻转
Collections.reverse(result);
return result;
}
}
四、二叉树的层序遍历的实现（leetcode 第102题）
-
上述的三种遍历方式（先序、中序、后序）采用的都是深度优先的方法，而二叉树的层序遍历的方式采用的是广度优先的实现方式。因此我们需要借助一个辅助的数据结构队列来进行实现，队列的先进先出的规则正好符合一层一层遍历的逻辑，而栈的先进后出的规则符合深度优先的遍历逻辑。
-
层序遍历的迭代实现
/*
思路：上面我们刚刚说了可以采用队列这种数据结构来进行辅助遍历操作。
这里的思路非常的简单，先将根节点入队列，然后进行输出，判断是否存在左右子节点，有的话就将左右子节点入队列，然后继续上述的操作，直到队列为空。
*/
class Solution {
public List<List<Integer>> levelOrder(TreeNode root) {
//首先创建一个列表来存储结果，一个队列来进行遍历操作
List<List<Integer>> result = new ArrayList<>();
Deque<TreeNode> deque = new ArrayDeque<>();
TreeNode temp = null;
int count = 0;
//先判断 root 是否为空
if(root == null){
return result;
}
//如果root不为空，先将root入队列
deque.add(root);
//循环结束的条件为队列为空了
while(!deque.isEmpty()){
//首先创建一个空的列表来每次存储每次出的元素
List<Integer> levelRes = new ArrayList<>();
count = deque.size();
for(int i = 0;i < count;i++){//注意如果直接deque.size()的话会存在问题，因为后序会添加，队列长度在发生改变，所以利用一个变量来代替
temp = deque.poll();
if(temp.left != null){
deque.add(temp.left);
}
if(temp.right != null){
deque.add(temp.right);
}
levelRes.add(temp.val);
}
result.add(levelRes);
//levelRes.clear();
}
return result;
}
} -
层序遍历的递归实现
/*
思路分析：首先得搞清楚递归的逻辑。我们这里还是同样采用先序遍历的方式来实现层级遍历。这里和先序遍历的方式不同之处在于，先序遍历我们是将中间节点的值直接添加到结果列表中。而这里我们采用的方法是，每次经过一次深度，就创建一个相应的子元素列表，然后添加到相应的子列表当中。
递归三部曲走起：
1.确定递归的参数与返回值。
参数：遍历的节点，已经树的深度。
返回值：没有必要返回值，本质上还是添加元素值。
private void level(TreeNode root, int depth)
2.确定递归的终止条件。
显然还是一样遇到空节点的时候进行返回。
if(root == null) return;
3.确定每层的递归逻辑。
每次发现层数比结果列表中的元素多时就添加一个结果列表的元素。然后再将该节点的值添加到创建的子元素列 表当中。
depth++;
if(depth > result.size()){
List<Integer> item = new ArrayList<>();
result.add(item);
}
result.get(depth - 1).add(root.val);
*/
class Solution {
//定义一个结果列表
List<List<Integer>> result = new ArrayList<>();
//递归实现方法
private void level(TreeNode root, int depth){
//递归终止条件
if(root == null){
return;
}
//每层递归逻辑（中间节点操作）
depth++;
if(depth > result.size()){
List<Integer> item = new ArrayLis<>();
result.add(item);
}
result.get(depth - 1).add(root.val);
level(root.left, depth); //左
level(root.right, depth); //右
}
public List<List<Integer>> levelOrder(TreeNode root) {
level(root, 0);
return result;
}
}