二叉树的遍历

1
void preoerder(treeNode* root) {
2
    if (!root) {
3
        return;
4
    }
5
    cout << root->val << " ";   //根   leetcode一般存到一个数组里
6
    preoerder(root->left);      //左
7
    preoerder(root->right);     //右
8
}
9
#### ✅ 迭代实现：
10

11

12
```cpp
13
void preorder(TreeNode* root) {
14
    if (!root) return;
15
    stack<TreeNode*> st;
16
    st.push(root);
17
    while (!st.empty()) {
18
        TreeNode* node = st.top(); st.pop();
19
        cout << node->val << " ";
20
        if (node->right) st.push(node->right);  // 注意：先右
21
        if (node->left) st.push(node->left);
22
    }
23
}
24
### 二、中序遍历（Inorder Traversal）
25

26

27
#### ✅ 顺序：
28

29

30
#### 左 → 根 → 右
31

32

33
#### ✅ 递归代码：
34

35

36
```cpp
37
void inorder(TreeNode* root) {
38
    if (!root) return;
39
    inorder(root->left);          // 遍历左子树
40
    cout << root->val << " ";     // 访问根
41
    inorder(root->right);         // 遍历右子树
42
}
43
#### ✅ 迭代实现：
44

45

46
```cpp
47
class Solution {
48
public:
49
    vector<int> inorderTraversal(TreeNode* root) {
50
        vector<int> result;
51
        stack<TreeNode*> st;
52
        TreeNode* cur = root;
53
        while (cur != NULL || !st.empty()) {
54
            if (cur != NULL) { // 指针来访问节点，访问到最底层
55
                st.push(cur); // 将访问的节点放进栈
56
                cur = cur->left;                // 左
57
            } else {
58
                cur = st.top(); // 从栈里弹出的数据，就是要处理的数据（放进result数组里的数据）
59
                st.pop();
60
                result.push_back(cur->val);     // 中
61
                cur = cur->right;               // 右
62
            }
63
        }
64
        return result;
65
    }
66
};
67
### 三、后序遍历（Postorder Traversal）
68

69

70
#### ✅ 顺序：
71

72

73
#### 左 → 右 → 根
74

75

76
#### ✅ 递归代码：
77

78

79
```cpp
80
void postorder(TreeNode* root) {
81
    if (!root) return;
82
    postorder(root->left);        // 遍历左子树
83
    postorder(root->right);       // 遍历右子树
84
    cout << root->val << " ";     // 访问根
85
}
86
#### ✅ 迭代技巧实现：
87

88

89
**方法：“根->右->左”后反转**
90

91

92
```cpp
93
void postorder(TreeNode* root) {
94
    if (!root) return;
95
    stack<TreeNode*> st;
96
    vector<int> result;
97
    st.push(root);
98
    while (!st.empty()) {
99
        TreeNode* node = st.top(); st.pop();
100
        result.push_back(node->val); // 根
101
        if (node->left) st.push(node->left);   // 左
102
        if (node->right) st.push(node->right); // 右
103
    }
104
    reverse(result.begin(), result.end());
105
    for (int v : result) cout << v << " ";
106
}
107
### 四、层序遍历（Level-order Traversal）
108

109

110
**✅ 顺序：**
111

112

113
#### 按层访问，每层从左到右
114

115

116
**✅ 使用队列（queue）**
117

118

119
```cpp
120
vector<vector<int>> levelOrder(TreeNode* root) {
121
    queue<TreeNode*> que;
122
    if (root != NULL) que.push(root);
123
    vector<vector<int>> result;
124
    while (!que.empty()) {
125
        int size = que.size();
126
        vector<int> vec;
127
        for (int i = 0; i < size; i++) {
128
            TreeNode* node = que.front(); que.pop();
129
            vec.push_back(node->val);
130
            if (node->left) que.push(node->left);
131
            if (node->right) que.push(node->right);
132
        }
133
        result.push_back(vec);
134
    }
135
    return result;
136
}