LeetCode36 - 二叉树的中序遍历

📝 题目描述

给定一个二叉树的根节点 root ，返回它的 中序遍历 。

示例：

示例 1：

1 2	输入：root = [1,null,2,3] 输出：[1,3,2]

示例 2：

1 2	输入：root = [] 输出：[]

示例 3：

1 2	输入：root = [1] 输出：[1]

提示：

树中节点数目在范围 [0, 100] 内
-100 <= Node.val <= 100

💡 解题思路

方法一：递归

二叉树的中序遍历：按照访问左子树——根节点——右子树的方式遍历这棵树，并且在访问左子树或者右子树的时候我们按照同样的方式遍历，直到遍历完整棵树。

因此整个遍历过程天然具有递归的性质，我们可以直接用递归函数来模拟这一过程。

方法二：迭代

方法一的递归函数我们也可以用迭代的方式实现，两种方式是等价的，区别在于递归的时候隐式地维护了一个栈，而我们在迭代的时候需要显式地将这个栈模拟出来，其他都相同。

★方法三：Morris 中序遍历

Morris 遍历算法是另一种遍历二叉树的方法，它能将非递归的中序遍历空间复杂度降为 $O(1)$ 。

Morris 遍历算法整体步骤如下（假设当前遍历到的节点为 $x$ ）：

如果 $x$ 无左孩子，先将 $x$ 的值加入答案数组，再访问 $x$ 的右孩子，即 $x=x.right$ 。
如果 $x$ $x$ 有左孩子，则找到 $x$ $x$ 左子树上最右的节点（即左子树中序遍历的最后一个节点， $x$ $x$ 在中序遍历中的前驱节点），我们记为 $predecessor$ $p re d ecessor$ 。根据 $predecessor$ $p re d ecessor$ 的右孩子是否为空，进行如下操作。
- 如果 $predecessor$ 的右孩子为空，则将其右孩子指向 $x$ ，然后访问 $x$ 的左孩子，即 $x=x.left$ 。
- 如果 $predecessor$ 的右孩子不为空，则此时其右孩子指向 $x$ ，说明我们已经遍历完 $x$ 的左子树，我们将 $predecessor$ 的右孩子置空，将 $x$ 的值加入答案数组，然后访问 $x$ 的右孩子，即 $x=x.right$ 。
重复上述操作，直至访问完整棵树。

🔧 代码实现

1、递归

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
    vector<int> ans;
public:
    void midTraversal(TreeNode* root) {
        if (!root) return;
        midTraversal(root -> left);
        ans.push_back(root -> val);
        midTraversal(root -> right);
    }
    vector<int> inorderTraversal(TreeNode* root) {
        midTraversal(root);
        return ans;
    }
};

2、迭代

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> ans;
        if (!root) return ans; 
        stack<TreeNode*> stk;
        TreeNode* curr = root;
        while(!stk.empty() || curr) {
            // 不断向左
            if (curr) {
                stk.push(curr);
                curr = curr -> left;
            } else {
                // 没有左子树，先处理根节点
                curr = stk.top();
                stk.pop();
                ans.push_back(curr -> val);
                // 转向处理右子树
                curr = curr -> right;
            }
        }
        return ans;
    }
};

3、Morris 中序遍历

class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> res;
        TreeNode *predecessor = nullptr;

        while (root != nullptr) {
            if (root->left != nullptr) {
                // predecessor 节点就是当前 root 节点向左走一步，然后一直向右走至无法走为止
                predecessor = root->left;
                while (predecessor->right != nullptr && predecessor->right != root) {
                    predecessor = predecessor->right;
                }
                
                // 让 predecessor 的右指针指向 root，继续遍历左子树
                if (predecessor->right == nullptr) {
                    predecessor->right = root;
                    root = root->left;
                }
                // 说明左子树已经访问完了，我们需要断开链接
                else {
                    res.push_back(root->val);
                    predecessor->right = nullptr;
                    root = root->right;
                }
            }
            // 如果没有左孩子，则直接访问右孩子
            else {
                res.push_back(root->val);
                root = root->right;
            }
        }
        return res;
    }
};

📊 复杂度分析

1、递归

时间复杂度： $O(n)$ ，其中 n 为二叉树节点的个数。二叉树的遍历中每个节点会被访问一次且只会被访问一次。
空间复杂度： $O(n)$ ，空间复杂度取决于递归的栈深度，而栈深度在二叉树为一条链的情况下会达到 $O(n)$ 的级别。

2、迭代

时间复杂度： $O(n)$ ，其中 n 为二叉树节点的个数。二叉树的遍历中每个节点会被访问一次且只会被访问一次。
空间复杂度： $O(n)$ ，空间复杂度取决于栈深度，而栈深度在二叉树为一条链的情况下会达到 O(n) 的级别。

3、Morris 中序遍历

时间复杂度： $O(n)$ ，其中 n 为二叉树的节点个数。Morris 遍历中每个节点会被访问两次，因此总时间复杂度为 $O(2n)=O(n)$ 。
空间复杂度： $O(1)$ 。

🎯 总结

核心思想：递归和迭代方法都要熟练掌握。