Space Cowboy

生死去来 棚头傀儡 一线断时 落落磊磊

0%

二叉树的遍历

发表于 更新于 分类于

简述

二叉树的遍历是解 leetcode 树类型题目的基础。搞清楚每一种遍历的细节和复杂度是解题的关键。
leetcode 上有很多相关的题目，但题解却经常只关注唯一的一道题。比如后序遍历就是利用稍微修改后的前序遍历倒置解出的，思路很巧妙，但是这种方法不具有普适性，无法解答其他与后序遍历相关的题目。
所以在这里完全总结一下二叉树遍历的问题，以便不仅仅可以写出题目，更重要的是在实际应用，比如模板解析中应用这些思路。
尽管对于二叉树来说，分为前中后序三种深度优先遍历和广度优先遍历四种。但实际上三种深度优先遍历不过是改变了访问子树根节点的时机，所以事实上可以认为是同一种遍历方式。

BeforeEach

我们约定树节点的数据类型如下，后不再赘述：

1
2
3
4
5
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

前序遍历

前序遍历是深度优先遍历，顺序是根节点 -> 左子树 -> 右子树。
所以你可以看到，这种方式是先处理子树根节点，再缓存左子树，最后处理右子树。

递归

对于树遍历的处理，天然的可以使用递归来处理。因为处理根和子树的逻辑是一样的，区别仅仅是我们需要根据不同的情况，来改变遍历（缓存）顺序。

1
2
3
4
5
6
7
8
9
10
def preorderTraversal(root: TreeNode):
    def visit(node):
        if not node: return
        res.append(node.val)
        visit(node.left)
        visit(node.right)

    res = []
    preorder(root)
    return res

二叉树中的每一个节点都被访问了，所以时间复杂度为 O(n)
递归过程中有栈的空间开销，对于二叉树，平均空间复杂度为 O(logn)，最差情况下树呈现链状，空间复杂度为 O(n)

迭代

递归实质上是代码自身通过函数调用栈隐式的维护了待处理节点的栈。所以我们也可以自己维护这个栈。你可以直接使用 list 来模拟栈，不过 collections 模块有个 deque 实现了头尾添加删除相同的速度，所以你也可以使用这个模块。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def preorderTraversal(root: TreeNode):
    if not root: return

    stack = [root]
    res = []

    while stack:
        cur = stack.pop()
        res.append(cur.val)
        if res.right:
            stack.append(res.right)
        if res.left:
            stack.append(res.left)

    return res

你应该注意到了，我们在向栈内添加子树的时候，是先添加右子树，后添加左子树。这主要是因为模拟的栈和递归隐式处理的调用栈是不同的。
递归时，我们不仅可以处理当前节点，还能缓存未处理节点的所有信息，这个信息不仅仅包含其本身的数据，还有对其要做的操作。换句话说，递归时我们并不知道接下来的处理路线。
而迭代时，我们是实际上是要借用栈这个数据结构来模拟出一个树的节点遍历顺序。而处理的顺序是从栈顶弹出，所以我们这里先压入左子树，再压入右子树。换句话说，迭代时我们知道将要处理的节点清单。

更进一步的，为什么我们不能使用队列？
因为树的遍历有一个特点，就是在深度优先遍历中，我们不能遇到什么节点就处理好什么节点。换句话说，我们会缓存一些待处理的节点，而这些待处理节点的处理时机则是先遇到的后处理，即先进后出，符合栈的逻辑。

时间复杂度与空间复杂度的分析同递归。原因是我们在这里也是模拟的递归调用栈。

Morris 遍历