二叉树的遍历方式
二叉树主要有两种遍历方式：
1.深度优先遍历：先往深走，遇到叶子节点再往回走。
2.广度优先遍历：一层一层的去遍历。
深度优先遍历：
前序遍历（递归法，迭代法）
中序遍历（递归法，迭代法）
后序遍历（递归法，迭代法）
广度优先遍历：
层次遍历（迭代法）
本文将对前中后序遍历进行详解。
前中后序指的就是中间节点的位置。看如下中间节点的顺序，就可以发现，中间节点的顺序就是所谓的遍历方式：
前序遍历：中左右
中序遍历：左中右
后序遍历：左右中
而二叉树的遍历，主要可以用到递归和迭代两种方法。
这里给出前中后序的LeetCode题目：
二叉树的前序遍历
给你二叉树的根节点 root ，返回它节点值的 前序 遍历。
示例 1：
输入：root = [1,null,2,3]
输出：[1,2,3]
示例 2：
输入：root = []
输出：[]
示例 3：
输入：root = [1]
输出：[1]
示例 4：
输入：root = [1,2]
输出：[1,2]
示例 5：
输入：root = [1,null,2]
输出：[1,2]
提示：
树中节点数目在范围 [0, 100] 内
-100 <= Node.val <= 100
二叉树的中序遍历
定一个二叉树的根节点 root ，返回 它的 中序 遍历 。
示例 1：
输入：root = [1,null,2,3]
输出：[1,3,2]
示例 2：
输入：root = []
输出：[]
示例 3：
输入：root = [1]
输出：[1]
提示：
树中节点数目在范围 [0, 100] 内
-100 <= Node.val <= 100
进阶: 递归算法很简单，你可以通过迭代算法完成吗？
二叉树的后序遍历
给你一棵二叉树的根节点 root ，返回其节点值的 后序遍历 。
示例 1：
输入：root = [1,null,2,3]
输出：[3,2,1]
示例 2：
输入：root = []
输出：[]
示例 3：
输入：root = [1]
输出：[1]
提示：
树中节点的数目在范围 [0, 100] 内
-100 <= Node.val <= 100
进阶：递归算法很简单，你可以通过迭代算法完成吗？
二叉树的递归法遍历
首先我们介绍递归法遍历，我们在使用递归法进行遍历二叉树的时候需要确定三个条件：
1.确定递归函数的参数和返回值。
2.确定终止条件。
3.确定单层递归的逻辑。
而对于递归法，前中后序的代码逻辑非常相似，只需要调整顺序即可，这里贴出递归法遍历的Java代码。
前序遍历：
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> list = new ArrayList<>();
if (root == null) {return list;}
preOrder(root, list);
return list;
}
public void preOrder(TreeNode root, List<Integer> list) {
if (root == null) {return;}
list.add(root.val);
preOrder(root.left, list);
preOrder(root.right, list);
}
}
中序遍历：
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> list = new ArrayList<>();
if (root == null) {return list;}
inOrder(root, list);
return list;
}
public void inOrder(TreeNode root, List<Integer> list) {
if (root == null) {return;}
inOrder(root.left, list);
list.add(root.val);
inOrder(root.right, list);
}
}
后序遍历：
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public List<Integer> postorderTraversal(TreeNode root) {
List<Integer> list = new ArrayList<>();
if (root == null) {return list;}
postOrder(root, list);
return list;
}
public void postOrder(TreeNode root, List<Integer> list) {
if (root == null) {return;}
postOrder(root.left, list);
postOrder(root.right, list);
list.add(root.val);
}
}
二叉树的迭代遍历
二叉树的迭代遍历要比递归遍历稍微复杂一些，我们需要使用到栈（先进后出）。且普通的迭代遍历，对于前中后序遍历的逻辑有一定的不同。
前序遍历：
我们先来看前序遍历，
前序遍历是中左右，每次先处理的是中间节点，那么先将根节点放入栈中，然后将右孩子加入栈，再加入左孩子。为什么要先加入 右孩子，再加入左孩子呢？ 因为这样出栈的时候才是中左右的顺序。
首先将根节点放入栈中，然后将其出栈，再将右孩子和左孩子分别压入栈中。
这样出栈的顺序就和前序遍历的顺序一致了。
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> list = new ArrayList<>();
if (root == null) {return list;}
Stack<TreeNode> stack = new Stack<>();
stack.push(root);
while (!stack.isEmpty()) {
TreeNode node = stack.pop();
list.add(node.val);
if (node.right != null) {
stack.push(node.right);
}
if (node.left != null) {
stack.push(node.left);
}
}
return list;
}
}
中序遍历：
使用迭代法进行中序遍历的逻辑就和前序遍历不太一样了。
因为前序遍历的顺序是中左右，先访问的元素是中间节点，要处理的元素也是中间节点，所以刚刚才能写出相对简洁的代码，因为要访问的元素和要处理的元素顺序是一致的，都是中间节点。
那么再看看中序遍历，中序遍历是左中右，先访问的是二叉树顶部的节点，然后一层一层向下访问，直到到达树左面的最底部，再开始处理节点（也就是在把节点的数值放进result数组中），这就造成了处理顺序和访问顺序是不一致的。
那么在使用迭代法写中序遍历，就需要借用指针的遍历来帮助访问节点，栈则用来处理节点上的元素。
即定义一个cur指针，当cur指针不为null时，将它指向的节点压入栈中，然后让它指向该节点的左孩子。也就是先将根节点的所有左孩子入栈。当cur为null时说明上一个节点没有左孩子，那就将该节点出栈并加入到result中，再让cur指向该节点的右孩子。
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> list = new ArrayList<>();
if (root == null) {return list;}
Stack<TreeNode> stack = new Stack<>();
TreeNode cur = root;
while (cur != null || !stack.isEmpty()) {
if (cur != null) {
stack.push(cur);
cur = cur.left;
}else {
cur = stack.pop();
list.add(cur.val);
cur = cur.right;
}
}
return list;
}
}
后序遍历：
使用迭代法进行后序遍历的思路和前序遍历比较相似。
先序遍历是中左右，后续遍历是左右中，那么我们只需要调整一下先序遍历的代码顺序，就变成中右左的遍历顺序，然后在反转result数组，输出的结果顺序就是左右中了。
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public List<Integer> postorderTraversal(TreeNode root) {
List<Integer> list = new ArrayList<>();
if (root == null) {return list;}
Stack<TreeNode> stack = new Stack<>();
stack.push(root);
//出栈顺序为中右左
while (!stack.isEmpty()) {
TreeNode node = stack.pop();
list.add(node.val);
if (node.left != null) {
stack.push(node.left);
}
if (node.right != null) {
stack.push(node.right);
}
}
//反转之后顺序为左右中，即后序遍历的顺序
Collections.reverse(list);
return list;
}
}
二叉树的统一迭代法
针对三种遍历方式，使用迭代法是可以写出统一风格的代码。
将访问的节点放入栈中，把要处理的节点也放入栈中但是要做标记。
如何标记呢，就是要处理的节点放入栈之后，紧接着放入一个空指针作为标记。 这种方法也可以叫做标记法。
将访问的节点直接加入到栈中，但如果是处理的节点则后面放入一个空节点， 这样只有空节点弹出的时候，才将下一个节点放进结果集。
前序遍历：
压入栈的顺序：右-左-中，要处理节点为中。
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> list = new ArrayList<>();
if (root == null) {return list;}
Stack<TreeNode> stack = new Stack<>();
stack.push(root);
while (!stack.isEmpty()) {
TreeNode node = stack.peek();
if (node != null) {
stack.pop();
if (node.right != null) {
stack.push(node.right);
}
if (node.left != null) {
stack.push(node.left);
}
stack.push(node);
stack.push(null);
}else {
stack.pop();
node = stack.pop();
list.add(node.val);
}
}
return list;
}
}
中序遍历：
压入栈的顺序：右-中-左，要处理节点为中。
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> list = new ArrayList<>();
if (root == null) {return list;}
Stack<TreeNode> stack = new Stack<>();
stack.push(root);
while (!stack.isEmpty()) {
TreeNode node = stack.peek();
if (node != null) {
stack.pop();
if (node.right != null) {
stack.push(node.right);
}
stack.push(node);
stack.push(null);
if (node.left != null) {
stack.push(node.left);
}
}
else {
stack.pop();
node = stack.pop();
list.add(node.val);
}
}
return list;
}
}
后序遍历：
压入栈的顺序：中-右-左，要处理节点为中。
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public List<Integer> postorderTraversal(TreeNode root) {
List<Integer> list = new ArrayList<>();
if (root == null) {return list;}
Stack<TreeNode> stack = new Stack<>();
stack.push(root);
while (!stack.isEmpty()) {
TreeNode node = stack.peek();
if (node != null) {
stack.pop();
stack.push(node);
stack.push(null);
if (node.right != null) {
stack.push(node.right);
}
if (node.left != null) {
stack.push(node.left);
}
}
else {
stack.pop();
node = stack.pop();
list.add(node.val);
}
}
return list;
}
}
可以看到，这种统一的迭代方法只需要修改入栈的顺序即可，逻辑一致。
