1
2
3
4
5
6

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

1
2
3
4
5
6

void preorder(TreeNode* root, vector<int>& res) {
    if (!root) return;
    res.push_back(root->val);    // 根
    preorder(root->left, res);   // 左
    preorder(root->right, res);  // 右
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

vector<int> preorderTraversal(TreeNode* root) {
    vector<int> res;
    stack<TreeNode*> st;
    if (root) st.push(root);

    while (!st.empty()) {
        TreeNode* node = st.top();
        st.pop();
        res.push_back(node->val);
        // 栈是先进后出，所以先压右再压左
        if (node->right) st.push(node->right);
        if (node->left) st.push(node->left);
    }
    return res;
}

1
2
3
4
5
6

void inorder(TreeNode* root, vector<int>& res) {
    if (!root) return;
    inorder(root->left, res);    // 左
    res.push_back(root->val);    // 根
    inorder(root->right, res);   // 右
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

vector<int> inorderTraversal(TreeNode* root) {
    vector<int> res;
    stack<TreeNode*> st;
    TreeNode* cur = root;

    while (cur || !st.empty()) {
        // 一路往左走，全部压栈
        while (cur) {
            st.push(cur);
            cur = cur->left;
        }
        // 弹出最左节点
        cur = st.top();
        st.pop();
        res.push_back(cur->val);
        // 处理右子树
        cur = cur->right;
    }
    return res;
}

1
2
3
4
5
6

void postorder(TreeNode* root, vector<int>& res) {
    if (!root) return;
    postorder(root->left, res);   // 左
    postorder(root->right, res);  // 右
    res.push_back(root->val);     // 根
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

vector<int> postorderTraversal(TreeNode* root) {
    vector<int> res;
    stack<TreeNode*> st;
    if (root) st.push(root);

    while (!st.empty()) {
        TreeNode* node = st.top();
        st.pop();
        res.push_back(node->val);
        // 先左后右，得到根右左
        if (node->left) st.push(node->left);
        if (node->right) st.push(node->right);
    }
    reverse(res.begin(), res.end());  // 翻转得到左右根
    return res;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

vector<vector<int>> levelOrder(TreeNode* root) {
    vector<vector<int>> res;
    if (!root) return res;

    queue<TreeNode*> q;
    q.push(root);

    while (!q.empty()) {
        int size = q.size();  // 当前层的节点数
        vector<int> level;
        for (int i = 0; i < size; i++) {
            TreeNode* node = q.front();
            q.pop();
            level.push_back(node->val);
            if (node->left) q.push(node->left);
            if (node->right) q.push(node->right);
        }
        res.push_back(level);
    }
    return res;
}

 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

vector<int> morrisInorder(TreeNode* root) {
    vector<int> res;
    TreeNode* cur = root;

    while (cur) {
        if (!cur->left) {
            res.push_back(cur->val);
            cur = cur->right;
        } else {
            TreeNode* prev = cur->left;
            while (prev->right && prev->right != cur) {
                prev = prev->right;
            }
            if (!prev->right) {
                prev->right = cur;
                cur = cur->left;
            } else {
                prev->right = nullptr;
                res.push_back(cur->val);
                cur = cur->right;
            }
        }
    }
    return res;
}

1
2
3
4

终止条件：if (!root) return;
处理根：res.push_back(root->val);
递归左：dfs(root->left);
递归右：dfs(root->right);