时间轴

2026-03-14

init

题目：

P94 二叉树的中序遍历

https://leetcode.cn/problems/binary-tree-inorder-traversal/description/?envType=study-plan-v2&envId=top-100-liked

用的是非递归写法

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
52
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)
        {
        }
};

#include <vector>
#include <stack>
using std::stack;
using std::vector;

class Solution {
    public:
        vector<int> inorderTraversal(TreeNode *root)
        {
                stack<TreeNode *> stk;
                TreeNode *p = root;
                vector<int> ret;

                while (p || !stk.empty()) {
                        if (p) {
                                stk.push(p);
                                p = p->left;
                        } else {
                                p = stk.top();
                                stk.pop();
                                ret.push_back(p->val); // visit p
                                p = p->right;
                        }
                }

                return ret;
        }
};