二叉树的遍历是数据结构中的一个经典问题，我们常用两种方式来进行遍历：递归，非递归。递归方式很容易理解和实现，但是在数据量大的情况下，递归层级太深，会导致虚拟机栈的栈溢出，系统稳定性会很差。所以在生产一般不会使用递归来实现。接下来，我们讲一下这四种遍历的非递归写法。
首先，我们定义一个二叉树：
前序遍历
前序遍历，也叫做先序遍历。它的遍历规则是首先访问根结点然后遍历左子树，最后遍历右子树。在遍历左、右子树时，仍然先访问根结点，然后遍历左子树，最后遍历右子树。
根->左->右
这里，我们遍历的时候用到了另一个数据结构：栈。利用它先进后出的特点来实现遍历。下面我们通过画图来展示一下整个遍历过程。
- 首先是创建一个栈，根节点入栈。
- A出栈，并且存入结果中。获取A的左右节点BC，先右后左入栈。（保证左节点B先出栈）
- B出栈，并且存入结果中。获取B的左右节点DE，先右后左入栈。（保证左节点D先出栈）
- D出栈，并且存入结果中。获取D的左右节点FG，先右后左入栈。（保证左节点F先出栈）
- F出栈，并存入结果中。由于F没有左右节点，所以进行下次循环。
- G出栈，并存入结果中。由于G没有左右节点，所以进行下次循环。
- 以此类推，依次出栈E，C。直到栈为空。最终我们输出了结果ABDFGEC。
代码如下：
public static class TreeNode {
String val;
TreeNode left;
TreeNode right;
TreeNode(String x) { val = x; }
}
// 非递归（栈）先序遍历树
public static List<String> preorderTraversal(TreeNode root) {
List<String> res = new ArrayList<>();
if (root == null) return res;
Stack<TreeNode> stack = new Stack<>();
stack.push(root);
while (!stack.isEmpty()) {
TreeNode node = stack.pop();
res.add(node.val);
if (node.right != null) stack.push(node.right);
if (node.left != null) stack.push(node.left);
}
return res;
}中序遍历
中序遍历，它的遍历规则是首先遍历左子树然后访问根结点，最后遍历右子树。在遍历左、右子树时，仍然先遍历左子树，然后访问根结点，最后遍历右子树。
左->根->右
下面我们通过画图来展示一下整个遍历过程。
- 首先创建一个栈，并且定义一个指针，指向根节点。
- 先通过指针访问左子树直到最低端，并且将元素压入栈内。
- F出栈，并存入结果中。将结果T指向F的右节点。右节点为空，进入下次循环。
- D出栈，并存入结果中。将结果T指向D的右节点G。
- 指针访问G的左子树直到最低端，并且将元素压入栈内。
- G出栈，并存入结果中。将结果T指向G的右节点。右节点为空，进入下次循环。
- B出栈，并存入结果中。将结果T指向B的右节点E。
- 指针访问E的左子树直到最低端，并且将元素压入栈内。
- E出栈，并存入结果中。将结果T指向E的右节点。右节点为空，进入下次循环。
- A出栈，并存入结果中。将结果T指向A的右节点C。
- 指针访问C的左子树直到最低端，并且将元素压入栈内。
- C出栈，并存入结果中。将结果T指向C的右节点。循环结束。输出：FDGBEAC。
代码如下：
// 非递归（栈）中序遍历树
public static List<String> inorderTraversal(TreeNode root) {
List<String> result = new ArrayList<>();
Stack<TreeNode> stack = new Stack<>();
TreeNode current = root;
while (current != null || !stack.isEmpty()) {
// 访问左子树直到最左端
while (current != null) {
stack.push(current);
current = current.left;
}
// 访问栈顶元素（即最左端节点）
current = stack.pop();
result.add(current.val); // 访问节点值
// 转向右子树
current = current.right;
}
return result;
}后序遍历
后序遍历，它的遍历规则是首先遍历左子树，然后遍历右子树，最后访问根结点。在遍历左、右子树时，仍然先遍历左子树，然后遍历右子树，最后访问根结点。
左->右->根
下面我们通过画图来展示一下整个遍历过程。
- 首先是创建一个栈，根节点入栈。
- A出栈，并且存入结果中。获取A的左右节点BC，先左后右入栈。（保证右节点C先出栈）
这里我们发现，逻辑跟前序遍历差不多，只不过先右后左改成了先左后右。后面我就省略跳过了。最终，我们得到了一个结果。
看出什么了，是不是结果反了。所以，我们需要把结果倒序。我们可以再遍历一下，将结果倒序。也可以将结果存入栈中，利用先进后出的特点，将结果倒序。最终结果成FGDEBCA。
代码如下：
// 非递归（栈）后序遍历树
public static List<String> postorderTraversal(TreeNode root) {
List<String> result = new ArrayList<>();
Stack<TreeNode> stack = new Stack<>();
Stack<String> outputStack = new Stack<>(); // 用于存储后序遍历的结果
stack.push(root);
while (!stack.isEmpty()) {
TreeNode node = stack.pop();
outputStack.push(node.val); // 先将节点值放入输出栈中，这样可以保证后序访问的顺序
if (node.left != null) {
stack.push(node.left); // 先左后右，这样可以保证左子节点先于右子节点被处理
}
if (node.right != null) {
stack.push(node.right);
}
}
// 输出后序遍历的结果，注意这里是反转输出栈以得到正确的后序遍历顺序
while (!outputStack.isEmpty()) {
result.add(outputStack.pop());
}
return result;
}层级遍历
层级遍历，它的遍历规则是首先访问根结点，然后访问第二级，然后访问第三级，直到结束。
这里，我们遍历的时候用到了另一个数据结构：队列。利用它先进先出的特点来实现遍历。下面我们通过画图来展示一下整个遍历过程。
- 首先是创建一个队列，根节点入队。
- A出队，并且存入结果中。获取A的左右节点BC，先左后右入队。（保证左节点B先出队）
后面的逻辑跟前序遍历差不多，后面我就省略跳过了。最终，我们得到了一个结果ABCDEFG。
代码如下：
// 非递归（队列）层级遍历树
public static List<String> levelOrderTraversal(TreeNode root) {
List<String> res = new ArrayList<>();
if (root == null) return res;
Queue<TreeNode> queue = new LinkedList<>();
queue.add(root);
while (!queue.isEmpty()) {
TreeNode node = queue.poll();
res.add(node.val);
if (node.left != null) queue.add(node.left);
if (node.right != null) queue.add(node.right);
}
return res;
}至此，我们实现了二叉树的前序遍历，中序遍历，后序遍历，层级遍历。掌握这些数据结构，对我们编程思维有很大的帮助。