二叉树的中序遍历 | 秋招知识库

什么是中序遍历？

二叉树有三种常见的遍历方式：

前序遍历：根-左-右。先获取根节点值，再访问根的左子树，最后访问根的右子树。
中序遍历：左-根-右。先访问根的左子树，再获取根节点值，最后访问根的右子树。
后序遍历：左-右-根。先访问根的左子树，再访问根的右子树，最后获取根节点值。

对于中序遍历，我们有如下递归代码。不了解递归的同学，可以看视频讲解【基础算法精讲 09】。

Python 解法1C++ 解法1

python

class Solution:
    def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        def dfs(node: Optional[TreeNode]) -> None:
            if node is None:
                return
            dfs(node.left)       # 左
            ans.append(node.val) # 根（这行代码移到前面就是前序，移到后面就是后序）
            dfs(node.right)      # 右

        ans = []
        dfs(root)
        return ans

cpp

// C++ 版待补充

C++ 解法2

cpp

class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> ans;

        // lambda 递归
        auto dfs = [&](this auto&& dfs, TreeNode* node) -> void {
            if (node == nullptr) {
                return;
            }
            dfs(node->left);          // 左
            ans.push_back(node->val); // 根（这行代码移到前面就是前序，移到后面就是后序）
            dfs(node->right);         // 右
        };

        dfs(root);
        return ans;
    }
};

复杂度分析

时间复杂度： $O (n)$ ，其中 $n$ 是二叉树的节点个数。
空间复杂度： $O (h)$ ，其中 $h$ 是二叉树的高度。递归需要 $O (h)$ 的栈空间。返回值不计入。

能不能做到 $O (1)$ 空间？不能写递归，也不能用栈模拟递归。

请看下图：

Python 解法3C++ 解法3

python

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

        while root:
            if root.left:
                # 找 root 的前驱 pre：在中序遍历中，root 的上一个节点
                # 从 root.left 开始，一直向右走，直到走到尽头，或者遇到指向 root 的线索（回到 root 的路）
                pre = root.left
                while pre.right and pre.right is not root:
                    pre = pre.right

                # root 的左子树尚未访问
                if pre.right is None:
                    pre.right = root  # 建立线索（回到 root 的路），相当于把 pre.right 当作栈
                    root = root.left  # 访问左子树
                    continue

                # root 的左子树访问完毕，去掉线索，恢复原样
                pre.right = None  # 注：如果调用完 inorderTraversal 不再使用这棵二叉树，这行代码可以去掉

            # root 的左子树访问完毕
            ans.append(root.val)  # 记录当前节点的值
            root = root.right  # 如果有右子树就访问右子树，没有就顺着线索回到指向的节点

        return ans

cpp

// C++ 版待补充

C++ 解法4

cpp

class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> ans;

        while (root) {
            if (root->left) {
                // 找 root 的前驱 pre：在中序遍历中，root 的上一个节点
                // 从 root->left 开始，一直向右走，直到走到尽头，或者遇到指向 root 的线索（回到 root 的路）
                TreeNode* pre = root->left;
                while (pre->right && pre->right != root) {
                    pre = pre->right;
                }

                // root 的左子树尚未访问
                if (pre->right == nullptr) {
                    pre->right = root; // 建立线索（回到 root 的路），相当于把 pre->right 当作栈
                    root = root->left; // 访问左子树
                    continue;
                }

                // root 的左子树访问完毕，去掉线索，恢复原样
                pre->right = nullptr; // 注：如果调用完 inorderTraversal 不再使用这棵二叉树，这行代码可以去掉
            }

            // root 的左子树访问完毕
            ans.push_back(root->val); // 记录当前节点的值
            root = root->right; // 如果有右子树就访问右子树，没有就顺着线索回到指向的节点
        }

        return ans;
    }
};

复杂度分析

时间复杂度： $O (n)$ ，其中 $n$ 是二叉树的节点个数。虽然写了个二重循环，但二叉树的每条边至多访问三次：第一次寻找前驱、遍历二叉树、第二次寻找前驱。所以总的循环次数是 $O (n)$ 。
空间复杂度： $O (1)$ 。返回值不计入。

相似题目

读完本文后，读者可以尝试用 Morris 遍历实现另外两种二叉树的遍历：

分类题单

如何科学刷题？

我的题解精选（已分类）

欢迎关注 B站@灵茶山艾府

复杂度分析 ​

复杂度分析 ​

相似题目 ​

分类题单 ​

复杂度分析

复杂度分析

相似题目

分类题单