二叉树的中序遍历

1
class Solution {
2
public:
3
    vector<int> inorderTraversal(TreeNode* root) {
4
        vector<int> ans;
5
        dfs(root, ans);
6
        return ans;
7
    }
8
private:
9
    void dfs(TreeNode* node, vector<int>& out) {
10
        if (!node) return;
11
        dfs(node->left, out);   // 左
12
        out.push_back(node->val); // 根
13
        dfs(node->right, out);  // 右
14
    }
15
};

1
#include <stack>
2
#include <vector>
3

4
class Solution {
5
public:
6
    vector<int> inorderTraversal(TreeNode* root) {
7
        vector<int> ans;
8
        stack<TreeNode*> st;
9
        TreeNode* cur = root;
10

11
        while (cur || !st.empty()) {
12
            // 阶段 1: 一路向左压栈
13
            while (cur) {
14
                st.push(cur);
15
                cur = cur->left;
16
            }
17
            // 阶段 2: 弹栈并读取
18
            cur = st.top();
19
            st.pop();
20
            ans.push_back(cur->val);
21
            // 阶段 3: 转向右子树
22
            cur = cur->right;
23
        }
24
        return ans;
25
    }
26
};

1
class Solution {
2
public:
3
    vector<int> inorderTraversal(TreeNode* root) {
4
        vector<int> ans;
5
        TreeNode *cur = root, *pre;
6
        while (cur) {
7
            if (cur->left) {
8
                // 寻找左子树的最右节点（前驱）
9
                pre = cur->left;
10
                while (pre->right && pre->right != cur) pre = pre->right;
11

12
                if (!pre->right) {
13
                    pre->right = cur; // 建立回勾线索
14
                    cur = cur->left;
15
                    continue; // 继续向左探路
16
                } else {
17
                    pre->right = nullptr; // 任务完成，拆除线索
18
                }
19
            }
20
            ans.push_back(cur->val); // 访问根节点
21
            cur = cur->right;        // 向右（真子结点或回勾）
22
        }
23
        return ans;
24
    }
25
};