Binary Tree inorder Traversal

94. 二叉树的中序遍历

分析

中序遍历的顺序是：左子树 -> 根节点 -> 右子树

初始化数据结构
- 创建一个结果数组 res，用于存储中序遍历的结果
- 创建一个栈 stk，用于辅助遍历
模拟递归过程
- 向左下方向遍历：当前节点非空时，将当前节点压入栈，并将其移动到左子节点
- 回溯节点并访问右子树：如果当前节点为空（即到达左子树的最深处），从栈中弹出一个节点，访问该节点的值并存入结果数组，然后将当前节点移动到其右子节点
- 重复以上过程，直到栈为空且当前节点为空

时间复杂度

每个节点被访问两次（一次压入栈，一次弹出栈），因此时间复杂度为 O(n)，其中 n 是节点总数

空间复杂度

栈的深度取决于树的高度。在最坏情况下（如链状树），栈的空间复杂度为 O(n)；在平衡树中，栈的空间复杂度为 O(logn)

C++代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51


// 非递归
class Solution
{
public:
    vector<int> inorderTraversal(TreeNode* root)
    {
        std::vector<int> res;          // 存储中序遍历结果
        std::stack<TreeNode*> stk;     // 辅助栈

        while (root || !stk.empty())   // 当节点非空或栈非空时，继续遍历
        {
            // 一直向左走，将路径上的节点压入栈
            while (root)
            {
                stk.push(root);        // 压入栈
                root = root->left;     // 移动到左子节点
            }

            // 回溯：弹出栈顶节点
            root = stk.top();
            stk.pop();

            res.push_back(root->val);  // 访问节点值

            root = root->right;        // 转向右子树
        }

        return res;                    // 返回结果
    }
};


// 递归
class Solution {
public:
    std::vector<int> res;

    void dfs(TreeNode* root)
    {
      if (!root) return;
      dfs(root->left);
      res.push_back(root->val);
      dfs(root->right);
    }

    vector<int> inorderTraversal(TreeNode* root)
    {
      dfs(root);
      return res;
    }
};