用迭代法进行《94. 二叉树中序遍历》

如题，题目意思非常简单，就是写一个二叉树的中序遍历。如果我们用递归来实现，简直太简单了。

1
2
3
4
5
6
7
8
9
10

class Solution:
    def __init__(self):
        self.res = []
    def inorderTraversal(self, root: TreeNode) -> List[int]:
        if not root:
            return self.res
        self.inorderTraversal(root.left)
        self.res.append(root.val)
        self.inorderTraversal(root.right)
        return self.re

算法思路极其明确，中序遍历左子树，然后遍历根节点，然后中序遍历右子树，打完收工。这个算法的时间复杂度也很好分析，因为每个节点刚好访问了一次，所以复杂度是 O(n)。那么空间复杂度是多少呢？

咱们先来看看，如果我们要用迭代法写一个二叉树的中序遍历，应该怎么写呢？我们都知道，递归是利用函数调用隐含的栈，保存了中间的现场，如果我们要用迭代法，需要手动来控制栈，我原本以为这是手到擒来的一个过程，可以随手写出来的，没想到，我栽了个大跟头。

我原本的思路是这样的，如果我要中序遍历一棵树，那么很简单啊，我会按照中序遍历左子树，然后根节点，然后中序遍历右子树的顺序。那么我用一个栈，弹出第一个要遍历的树，先把右子树压栈，然后把根节点压栈，然后把左子树压栈。迭代这个过程。

这个过程竟然完全没有写对……不信，你可以不看下面的代码自己写写看。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

class Solution:
    def inorderTraversal(self, root: TreeNode) -> List[int]:
        stk, res = [root], []

        while stk:
            cur = stk.pop()
            if isinstance(cur, int):
                res.append(cur)
                continue
            if not cur:
                continue
            stk.append(cur.right)
            stk.append(cur.val)
            stk.append(cur.left)
        return res

当然，上面这个写法是对的，是我后来根据这个思路重写的。这里，我硬是把根节点的数字解出来和指针一起压进了栈里，才写出来了相对简洁的写法。不然，怎么判定当前的节点是不是根节点，就是个麻烦。

其实，这个思维相当于是广度优先了。每次访问一棵树，先按照正确的顺序，将树替换成下一层遍历的顺序，然后再顺次遍历。显然，还有更简洁的思路，就是按照深度优先的方式。我们遍历一棵树的时候，可以看成沿着树走迷宫，如果可以往左拐，就一直往左拐，一直到没有路了，我们再访问当前路口，然后，往右拐一下，再重复整个过程。

按这个思路写出代码：

1
2
3
4
5
6
7
8
9
10
11
12

class Solution:
    def inorderTraversal(self, root: TreeNode) -> List[int]:
        stk, res = [], []
        while root or stk:
            while root:
                stk.append(root)
                root = root.left
            cur = stk.pop()
            res.append(cur.val)
            root = cur.right

        return res

这个算法同样是用栈，但是却简洁很多了，也没有用到 isinstance 这种判断，非常规整，然而在思路上却不那么平铺直叙了。大家可以细细品味一下。

这就是我以前常说的，有时候嘴巴说得头头是道，未必写得出来。其实这也就是我们练习写代码的意义所在。