二叉树的中序遍历

算法
留言

一、引言

二叉树是计算机科学中一种非常重要的数据结构，而二叉树的遍历操作又是对二叉树进行操作的基础。其中，中序遍历是二叉树遍历中的一种常见方式。在这篇博客中，我们将深入探讨二叉树中序遍历的概念，并介绍三种实现中序遍历的方法：迭代法、递归法和Morris遍历法。

二、二叉树中序遍历的定义

中序遍历（Inorder Traversal）是二叉树遍历的一种方式，它按照“左 - 根 - 右”的顺序访问二叉树中的节点。也就是说，对于每个节点，先遍历其左子树，然后访问该节点本身，最后遍历其右子树。

例如，对于如下二叉树：

1
2
3
  1
 / \
2   3

其中序遍历的结果是 [2, 1, 3]。

三、迭代法实现中序遍历

  1. 算法思路
    • 迭代法实现中序遍历主要依靠栈这种数据结构。我们从根节点开始，将根节点及其所有左子节点依次压入栈中，直到左子节点为空。
    • 然后从栈中弹出一个节点，访问该节点（将其值添加到结果列表中），再处理该节点的右子树。
    • 重复上述过程，直到栈为空且当前节点为空。
  2. 代码实现（以Go语言为例）
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    func inorderTraversal(root *TreeNode) (res []int) {
        stack := []*TreeNode{}  // 也可以写成 stack := make([]*TreeNode, 0)
        for (root!= nil || len(stack)!= 0) {
            for root!= nil {
                stack = append(stack, root)
                root = root.Left
            }
            root = stack[len(stack)-1]
            stack = stack[:len(stack)-1]
            res = append(res, root.Val)
            root = root.Right
        }
        return
    }
  3. 代码解释
    • 首先，我们初始化一个空栈 stack。
    • 在主循环中，(root!= nil || len(stack)!= 0) 条件判断保证了只要还有节点未被遍历或者栈中还有节点，就继续循环。
    • 内层循环 for root!= nil 不断将当前节点及其左子节点压入栈中，直到当前节点的左子节点为空。
    • 当内层循环结束后，从栈顶弹出一个节点（这是最左的节点），将其值添加到结果列表 res 中，然后处理该节点的右子树。

四、递归法实现中序遍历

  1. 算法思路
    • 递归法实现中序遍历是基于二叉树中序遍历的定义。对于一个节点，先递归地遍历其左子树，然后访问该节点本身，最后递归地遍历其右子树。
  2. 代码实现（以Go语言为例）
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    func inorderTraversal(root *TreeNode) []int {
        var res []int
        var inorder func(*TreeNode)
        inorder = func(node *TreeNode) {
            if node == nil {
                return
            }
            inorder(node.Left)
            res = append(res, node.Val)
            inorder(node.Right)
        }
        inorder(root)
        return res
    }
  3. 代码解释
    • 我们定义了一个内部递归函数 inorder。
    • 当节点为 nil 时，直接返回，表示已经到达叶子节点的下一层（空节点）。
    • 首先递归调用 inorder(node.Left) 来遍历左子树，然后将当前节点的值添加到结果列表 res 中，最后递归调用 inorder(node.Right) 来遍历右子树。

五、Morris遍历法实现中序遍历

  1. 算法思路
    • Morris遍历法是一种利用树的空闲指针来实现空间复杂度为O(1)的遍历方法。它的核心思想是利用二叉树节点中的空指针来建立一种临时的链接，帮助我们实现遍历。
    • 对于当前节点，如果其左子节点为空，那么我们访问当前节点，并移动到右子节点。
    • 如果当前节点的左子节点不为空，我们找到当前左子树中的最右节点（即左子树中的前驱节点）。如果最右节点的右指针为空，我们将其右指针指向当前节点，然后移动到左子节点；如果最右节点的右指针指向当前节点，这意味着我们已经遍历完左子树，我们断开这个临时链接，访问当前节点，并移动到右子节点。
  2. 代码实现（以Go语言为例）
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    func inorderTraversal(root *TreeNode) []int {
        var res []int
        cur := root
        for cur!= nil {
            if cur.Left == nil {
                res = append(res, cur.Val)
                cur = cur.Right
            } else {
                prev := cur.Left
                for prev.Right!= nil && prev.Right!= cur {
                    prev = prev.Right
                }
                if prev.Right == nil {
                    prev.Right = cur
                    cur = cur.Left
                } else {
                    prev.Right = nil
                    res = append(res, cur.Val)
                    cur = cur.Right
                }
            }
        }
        return res
    }
  3. 代码解释
    • 我们从根节点开始，用 cur 指针来遍历二叉树。
    • 当 cur.Left == nil 时，我们直接访问当前节点（将其值添加到 res 中），然后移动到右子节点。
    • 当 cur.Left!= nil 时，我们寻找当前左子树中的最右节点 prev。
      • 如果 prev.Right == nil，说明我们还没有遍历左子树，我们将 prev.Right 指向当前节点 cur，然后移动到左子节点。
      • 如果 prev.Right == cur，说明我们已经遍历完左子树，我们断开这个临时链接（将 prev.Right 设为 nil），访问当前节点（将其值添加到 res 中），然后移动到右子节点。

六、总结

二叉树的中序遍历在很多算法问题中都有重要应用。迭代法利用栈来实现遍历，逻辑清晰但需要手动管理栈；递归法代码简洁明了，但在一些语言中可能会因为递归深度过深而导致栈溢出；Morris遍历法虽然算法思路较为复杂，但实现了空间复杂度为O(1)的遍历，在空间受限的情况下非常有用。根据不同的应用场景，我们可以选择合适的遍历方法来解决问题。