我们来看一个例子：
class Node: def __init__(self, val): self.val = val # 左孩子 self.lchild = None # 右孩子 self.rchild = None if __name__ == "__main__": # 建树 root = Node(0) node1 = Node(1) root.lchild = node1 node2 = Node(2) root.rchild = node2 node3 = Node(3) node1.lchild = node3 node4 = Node(4) node1.rchild = node4 node5 = Node(5) node2.rchild = node5这是一棵简单的二叉树，画出来是这个样子：
0 / \ 1 2 / \ \ 3 4 5下面我们要通过栈在不使用递归的情况下来中序遍历它，中序遍历我们都知道，就是先遍历左子树，然后输出当前节点，再遍历右子树。写成递归非常方便，只有几行：
def dfs(node): if node is None: return dfs(node.lchild) print(node.val) dfs(node.rchild)大家想想，如果不使用递归应该怎么办？如果你真的试着去写，就会发现看起来很简单的问题好像变得非常复杂。我们很容易可以想到，我们把节点存储在栈当中，但是存储数据只是表象。本质问题是当我们从栈当中拿到了一个节点之后，我们怎么判断它究竟应该做什么？应该遍历左节点吗，应该输出吗，还是应该遍历右节点？
对这些问题仔细分析和思考，我们可以发现它们都和递归的回溯有关。
在递归当中，当我们遍历完了当前节点的某棵子树之后，随着栈的弹出，还会回到这个节点。比如上面这棵树当中，在递归过程当中，我们会两次碰到1这个节点。第一次时它不会输出1，而是先去遍历了它的左子树，也就是3，之后再次回到1，由于它的左子树已经遍历过，所以会输出1。这个离开又回来的过程称为回溯。如果你把树结构想象成瀑布的话，这个过程有点像是顺流而下，又逆流而上，翻译成回溯还是蛮合理的。
我们回到之前的问题，所有的搞不清楚的本质都来源于我们无法判断当前遇到的节点究竟是初次见面，还是回溯之后的久别重逢。而这关系到我们要对它做什么。原本在递归当中，由于程序会记录递归时的状态和代码运行的位置，递归回溯之后会回到上次调用的位置，所以我们可以忽略这个问题。而现在我们由于不再使用递归，所以需要我们自己来判断节点的状态。
想通了其实很简单，我们只需要在节点当中加一个状态的字段，表示这个节点是否会发生回溯。显然在一开始的时候，所有的节点状态都是True。
class Node: def __init__(self, val): self.val = val self.lchild = None self.rchild = None self.flag = True我们在Node类中加一个flag作为记录，初始化时我们默认它为True。接着就很简单了，我们就按照左中右的顺序遍历节点，只要左子树存在就往左边遍历，在一路往左的过程中遇到的这些节点的flag全部置为False，因为它们的回溯已经开始，以后不会再发生回溯了。由于往右遍历不会存在回溯的问题，所以可以忽略，想明白了，代码也就顺理成章。
# 使用我们自己刚刚创建的数据结构 stack = Stack() # 插入根节点 stack.push(root) while not stack.is_empty(): # 获取栈顶元素，也就是当前遍历的节点 tmp = stack.top() # 如果不曾回溯过，并且左子树存在 while tmp.flag and tmp.lchild is not None: # 回溯标记置为False tmp.flag = False # 栈顶push左孩子 stack.push(tmp.lchild) # 往左遍历 tmp = tmp.lchild # 弹出栈顶 tmp = stack.pop() # 此时说明左节点已经遍历完了，输出 print(tmp.val) # 往右遍历 if tmp.rchild is not None: stack.push(tmp.rchild)这段代码虽然短，但其实不简单，想要完全看懂需要对递归和循环有深入的理解。属于典型的看着简单实际不容易的题，我个人比较喜欢这类问题，除了锻炼思维之外也很适合用来面试，候选人的思维能力、代码驾驭能力基本上都一清二楚了。没有看懂的同学也不用担心，因为在实际场景当中并不会遇到这样的场景，以后还会推出其他关于递归和搜索算法的文章，只要你坚持阅读，我相信一定会看懂的。
今天的文章就是这些，如果觉得有所收获，请顺手扫码点个关注吧，你们的举手之劳对我来说很重要。