• 03/16 401. 二进制手表 (1328 views)
• 03/17 怎么推导出《115. 不同的子序列》的动态规划解法 (1304 views)
• 03/27 338.比特位计数 (1064 views)
• 04/20 1006. 笨阶乘 (963 views)
• 03/15 54. 螺旋矩阵 & 59. 螺旋矩阵 II (856 views)
• 03/23 341. 扁平化嵌套列表迭代器 (799 views)
• 03/18 453. 最小操作次数使数组元素相等 (795 views)
• 03/14 367. 有效的完全平方数 (720 views)

• Charles : Sorry, 我测试了一下，有个语法特性在 PHP 7.0 下不支持，更新到 2.0.7 可以修复。...

• 大盛 : 你好，我启用后报错，怎么解决啊，我的WP版本是5.6.1，PHP版本是7.0

  Parse er...

• Wang : 现在大部分大学老师在照本宣科，学生在应付考试，计算机专业在大学毕业前没打开过GitHub大有人在。自...
• Charles : 我上面插图里，有我家里门禁室内机的电路板。电路板正面右上角，有一个开关，那个就是开锁按钮，可以看到就...
• 求教 : 您好，最近在研究类似方案，刚刚好搜到你的文章。虽然没有看到介绍，但是我看文章的情况，貌似您的门禁室内...

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

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)。那么空间复杂度是多少呢？

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

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

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

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

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

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

按这个思路写出代码：

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 这种判断，非常规整，然而在思路上却不那么平铺直叙了。大家可以细细品味一下。

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

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据。