LeetCode 第 94 题：“二叉树的中序遍历”题解
题解地址：模拟系统栈完成非递归中序遍历，同理可以完成非递归的前序遍历和后序遍历（Python 代码、Java 代码）。
说明：文本首发在力扣的题解版块，更新也会在第 1 时间在上面的网站中更新，这篇文章只是上面的文章的一个快照，您可以点击上面的链接看到其他网友对本文的评论。
传送门：94. 二叉树的中序遍历。
给定一个二叉树，返回它的中序 遍历。
示例:
输入: [1,null,2,3] 1
2 / 3输出: [1,3,2] 进阶: 递归算法很简单，你可以通过迭代算法完成吗？
模拟系统栈完成非递归中序遍历，同理可以完成非递归的前序遍历和后序遍历（Python 代码、Java 代码）
方法：模拟系统栈
模拟系统栈的方法其实并不难理解，就是在栈中放入结点的同时，同时传入一个指令，这个指令可以有 2 个含义：
1、递归执行（就是继续放入栈里）；
2、马上执行。
模拟系统栈的注意事项：因为栈是先进后出的，当递归执行的时候，代码编写的顺序应该是相应遍历种类的倒序（具体可以参考下面的代码）。
模拟系统栈的好处：稍微改动一下代码，就可以完成非递归的前序遍历和后序遍历。
参考代码：
Python 代码：
class TreeNode:
def __init__(self, x):
self.val = x
self.left = None
self.right = None
class Solution:
def inorderTraversal(self, root: TreeNode) -> List[int]:
if not root:
return []
# 1 表示递归处理
stack = [(1, root)]
res = []
while stack:
command, node = stack.pop()
if command == 0:
# 0 表示当前马上执行将结点的值添加到结果集中
res.append(node.val)
else:
# 关键在这里：因为是模拟系统栈，应该把中序遍历的顺序倒过来写
# 调整一下顺序就可以完成前序遍历和后序遍历
if node.right:
stack.append((1, node.right))
stack.append((0, node))
if node.left:
stack.append((1, node.left))
return res
Java 代码：
import java.util.ArrayList;
import java.util.List;
import java.util.Stack;
class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) {
val = x;
}
}
public class Solution {
private enum Action {
// GO 表示递归处理
// ADDTORESULT 表示当前马上执行将结点的值添加到结果集中
GO, ADDTORESULT
}
private class Command {
private Action action;
private TreeNode node;
public Command(Action action, TreeNode node) {
this.action = action;
this.node = node;
}
}
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> res = new ArrayList<>();
if (root == null) {
return res;
}
Stack<Command> stack = new Stack<>();
stack.add(new Command(Action.GO, root));
while (!stack.isEmpty()) {
Command command = stack.pop();
if (command.action == Action.ADDTORESULT) {
res.add(command.node.val);
} else {
assert command.action == Action.GO;
// 关键在这里：因为是模拟系统栈，应该把中序遍历的顺序倒过来写
// 调整一下顺序就可以完成前序遍历和后序遍历
if (command.node.right != null) {
stack.add(new Command(Action.GO, command.node.right));
}
stack.add(new Command(Action.ADDTORESULT, command.node));
if (command.node.left != null) {
stack.add(new Command(Action.GO, command.node.left));
}
}
}
return res;
}
}