1
struct TreeNode {
2
    int val;
3
    TreeNode* left;
4
    TreeNode* right;
5
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
6
};
7

8
// 递归版——最直觉
9
void preorder(TreeNode* root, std::vector<int>& result) {
10
    if (!root) return;
11
    result.push_back(root->val);  // 根
12
    preorder(root->left, result);  // 左
13
    preorder(root->right, result); // 右
14
}
15

16
// 包装版
17
std::vector<int> preorderTraversal(TreeNode* root) {
18
    std::vector<int> result;
19
    preorder(root, result);
20
    return result;
21
}

1
std::vector<std::vector<int>> levelOrder(TreeNode* root) {
2
    std::vector<std::vector<int>> result;
3
    if (!root) return result;
4

5
    std::queue<TreeNode*> q;
6
    q.push(root);
7

8
    while (!q.empty()) {
9
        int level_size = q.size();  // 关键：当前层的节点数
10
        std::vector<int> level;
11

12
        for (int i = 0; i < level_size; ++i) {
13
            TreeNode* node = q.front();
14
            q.pop();
15

16
            level.push_back(node->val);
17

18
            if (node->left)  q.push(node->left);
19
            if (node->right) q.push(node->right);
20
        }
21

22
        result.push_back(std::move(level));
23
    }
24
    return result;
25
}
26
// 时间 O(n), 空间 O(n)

1
std::vector<int> preorderIterative(TreeNode* root) {
2
    std::vector<int> result;
3
    if (!root) return result;
4

5
    std::stack<TreeNode*> stk;
6
    stk.push(root);
7

8
    while (!stk.empty()) {
9
        TreeNode* node = stk.top();
10
        stk.pop();
11

12
        result.push_back(node->val);  // 根
13

14
        // 先压右，再压左 → 出栈时左先于右
15
        if (node->right) stk.push(node->right);
16
        if (node->left)  stk.push(node->left);
17
    }
18
    return result;
19
}

1
std::vector<int> inorderIterative(TreeNode* root) {
2
    std::vector<int> result;
3
    std::stack<TreeNode*> stk;
4
    TreeNode* curr = root;
5

6
    while (curr || !stk.empty()) {
7
        // 一路向左，把沿途节点全压栈
8
        while (curr) {
9
            stk.push(curr);
10
            curr = curr->left;
11
        }
12

13
        // 弹出栈顶 = 当前最左的未处理节点
14
        curr = stk.top();
15
        stk.pop();
16
        result.push_back(curr->val);  // 处理根
17

18
        // 转向右子树
19
        curr = curr->right;
20
    }
21
    return result;
22
}

1
        1
2
       / \
3
      2   3
4
     / \
5
    4   5
6

7
执行过程：
8
1. curr=1, 一路向左: push 1, push 2, push 4, curr=null
9
2. pop 4 → result=[4], curr=4.right=null
10
3. pop 2 → result=[4,2], curr=2.right=5
11
4. push 5, curr=5.left=null
12
5. pop 5 → result=[4,2,5], curr=5.right=null
13
6. pop 1 → result=[4,2,5,1], curr=1.right=3
14
7. push 3, curr=3.left=null
15
8. pop 3 → result=[4,2,5,1,3], curr=3.right=null
16
9. 栈空且 curr=null → 结束
17

18
结果: [4, 2, 5, 1, 3] ✅ (中序)

1
// 方法一：反转法（最易理解）
2
// 后序 = 左右根  ←→  反转（根右左）
3
std::vector<int> postorderIterative(TreeNode* root) {
4
    std::vector<int> result;
5
    if (!root) return result;
6

7
    std::stack<TreeNode*> stk;
8
    stk.push(root);
9

10
    while (!stk.empty()) {
11
        TreeNode* node = stk.top();
12
        stk.pop();
13

14
        result.push_back(node->val);  // 根
15

16
        // 先压左，再压右 → 出栈时右先于左 → "根右左"
17
        if (node->left)  stk.push(node->left);
18
        if (node->right) stk.push(node->right);
19
    }
20

21
    // 反转得到 "左右根"
22
    std::reverse(result.begin(), result.end());
23
    return result;
24
}

1
// 方法二：标记法（真正的后序，无需反转）
2
std::vector<int> postorderIterative_v2(TreeNode* root) {
3
    std::vector<int> result;
4
    std::stack<TreeNode*> stk;
5
    TreeNode* curr = root;
6
    TreeNode* last_visited = nullptr;
7

8
    while (curr || !stk.empty()) {
9
        // 一路向左
10
        while (curr) {
11
            stk.push(curr);
12
            curr = curr->left;
13
        }
14

15
        TreeNode* top = stk.top();
16

17
        // 如果右子树存在且未被访问过 → 先处理右子树
18
        if (top->right && top->right != last_visited) {
19
            curr = top->right;
20
        } else {
21
            // 右子树不存在或已处理 → 访问当前节点
22
            result.push_back(top->val);
23
            last_visited = top;
24
            stk.pop();
25
        }
26
    }
27
    return result;
28
}

1
// 统一迭代模板（以中序为例）
2
std::vector<int> unified_inorder(TreeNode* root) {
3
    std::vector<int> result;
4
    if (!root) return result;
5

6
    // pair<节点, 是否已标记>
7
    std::stack<std::pair<TreeNode*, bool>> stk;
8
    stk.push({root, false});
9

10
    while (!stk.empty()) {
11
        auto [node, visited] = stk.top();
12
        stk.pop();
13

14
        if (visited) {
15
            result.push_back(node->val);  // 已标记的直接输出
16
        } else {
17
            // 按 "右 → 根(标记) → 左" 入栈（栈是 LIFO，反过来就是中序）
18
            if (node->right) stk.push({node->right, false});
19
            stk.push({node, true});  // 标记当前节点
20
            if (node->left)  stk.push({node->left, false});
21
        }
22
    }
23
    return result;
24
}
25

26
// 前序只需改入栈顺序:  右 → 左 → 根(标记)
27
// 后序只需改入栈顺序:  根(标记) → 右 → 左

1
std::vector<int> morrisInorder(TreeNode* root) {
2
    std::vector<int> result;
3
    TreeNode* curr = root;
4

5
    while (curr) {
6
        if (!curr->left) {
7
            // 没有左子树：直接访问，转右
8
            result.push_back(curr->val);
9
            curr = curr->right;
10
        } else {
11
            // 有左子树：找前驱（左子树的最右节点）
12
            TreeNode* predecessor = curr->left;
13
            while (predecessor->right && predecessor->right != curr) {
14
                predecessor = predecessor->right;
15
            }
16

17
            if (!predecessor->right) {
18
                // 第一次到达：建立线索 → 前驱的 right 指向 curr
19
                predecessor->right = curr;
20
                curr = curr->left;  // 进入左子树
21
            } else {
22
                // 第二次到达：说明左子树已遍历完，断开线索
23
                predecessor->right = nullptr;  // 恢复原状
24
                result.push_back(curr->val);   // 访问根
25
                curr = curr->right;            // 进入右子树
26
            }
27
        }
28
    }
29
    return result;
30
}
31
// 时间 O(n), 空间 O(1)

1
初始:       4
2
           / \
3
          2   6
4
         / \ / \
5
        1  3 5  7
6

7
Step 1: curr=4, 找左子树的最右节点 = 3
8
        3.right = null → 建立线索: 3→4
9
        curr 进入左子树 → curr=2
10

11
Step 2: curr=2, 找左子树的最右节点 = 1
12
        1.right = null → 建立线索: 1→2
13
        curr 进入左子树 → curr=1
14

15
Step 3: curr=1, 没有左子树
16
        输出 1, curr=1.right=2 (线索！)
17

18
Step 4: curr=2, 找前驱 = 1, 1.right=2=curr → 第二次到达
19
        断开线索: 1.right=null
20
        输出 2, curr=2.right=3
21

22
Step 5: curr=3, 没有左子树
23
        输出 3, curr=3.right=4 (线索！)
24

25
Step 6: curr=4, 找前驱 = 3, 3.right=4=curr → 第二次到达
26
        断开线索: 3.right=null
27
        输出 4, curr=4.right=6
28

29
... 右子树同理 ...
30

31
结果: [1, 2, 3, 4, 5, 6, 7] ✅ (中序)

1
void _pathSum(TreeNode* node, int remaining,
2
              std::vector<int>& path,
3
              std::vector<std::vector<int>>& result)
4
{
5
    if (!node) return;
6

7
    path.push_back(node->val);
8
    remaining -= node->val;
9

10
    if (!node->left && !node->right && remaining == 0) {
11
        result.push_back(path);  // 找到一条路径
12
    }
13

14
    _pathSum(node->left, remaining, path, result);
15
    _pathSum(node->right, remaining, path, result);
16

17
    path.pop_back();  // 回溯！
18
}
19

20
std::vector<std::vector<int>> pathSum(TreeNode* root, int targetSum) {
21
    std::vector<std::vector<int>> result;
22
    std::vector<int> path;
23
    _pathSum(root, targetSum, path, result);
24
    return result;
25
}

1
int diameterOfBinaryTree(TreeNode* root) {
2
    int diameter = 0;
3
    _depth(root, diameter);
4
    return diameter;
5
}
6

7
int _depth(TreeNode* node, int& diameter) {
8
    if (!node) return 0;
9

10
    int left = _depth(node->left, diameter);
11
    int right = _depth(node->right, diameter);
12

13
    // 经过当前节点的最长路径 = 左深度 + 右深度
14
    diameter = std::max(diameter, left + right);
15

16
    return 1 + std::max(left, right);  // 返回深度给父节点
17
}
18
// 时间 O(n), 空间 O(h)

1
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
2
    // base case
3
    if (!root || root == p || root == q) return root;
4

5
    TreeNode* left = lowestCommonAncestor(root->left, p, q);
6
    TreeNode* right = lowestCommonAncestor(root->right, p, q);
7

8
    // 情况分析:
9
    // left && right: p 和 q 分布在两侧 → 当前节点就是 LCA
10
    // left 为空: p 和 q 都在右子树 → 返回 right
11
    // right 为空: p 和 q 都在左子树 → 返回 left
12
    if (left && right) return root;
13
    return left ? left : right;
14
}
15
// 时间 O(n), 空间 O(h)

1
TreeNode* buildTree(std::vector<int>& preorder, std::vector<int>& inorder) {
2
    // 用哈希表加速中序中的查找
3
    std::unordered_map<int, int> in_map;
4
    for (int i = 0; i < static_cast<int>(inorder.size()); ++i) {
5
        in_map[inorder[i]] = i;
6
    }
7

8
    int pre_idx = 0;
9
    return _build(preorder, pre_idx, in_map, 0, inorder.size() - 1);
10
}
11

12
TreeNode* _build(std::vector<int>& preorder, int& pre_idx,
13
                 std::unordered_map<int, int>& in_map,
14
                 int in_left, int in_right)
15
{
16
    if (in_left > in_right) return nullptr;
17

18
    int root_val = preorder[pre_idx++];
19
    TreeNode* root = new TreeNode(root_val);
20

21
    int in_root = in_map[root_val];  // 根在中序中的位置
22

23
    // 先构建左子树（前序中左子树紧跟在根后面）
24
    root->left  = _build(preorder, pre_idx, in_map, in_left, in_root - 1);
25
    root->right = _build(preorder, pre_idx, in_map, in_root + 1, in_right);
26

27
    return root;
28
}
29
// 时间 O(n), 空间 O(n)

1
preorder = [3, 9, 20, 15, 7]
2
inorder  = [9, 3, 15, 20, 7]
3

4
Step 1: 前序第一个 = 3 → 根
5
        在中序中找 3 → 位置 1
6
        中序左子树: [9]     中序右子树: [15, 20, 7]
7

8
Step 2: 前序下一个 = 9 → 左子树的根
9
        在中序中找 9 → 位置 0
10
        [9] 左右都为空 → 叶节点
11

12
Step 3: 前序下一个 = 20 → 右子树的根
13
        在中序中找 20 → 位置 3
14
        左: [15]  右: [7]
15

16
结果:    3
17
        / \
18
       9  20
19
         /  \
20
        15   7

1
class Codec {
2
public:
3
    // 前序序列化
4
    std::string serialize(TreeNode* root) {
5
        if (!root) return "null,";
6
        return std::to_string(root->val) + ","
7
             + serialize(root->left)
8
             + serialize(root->right);
9
    }
10

11
    // 反序列化
12
    TreeNode* deserialize(const std::string& data) {
13
        std::queue<std::string> tokens;
14
        std::string token;
15
        for (char c : data) {
16
            if (c == ',') {
17
                tokens.push(token);
18
                token.clear();
19
            } else {
20
                token += c;
21
            }
22
        }
23

24
        return _build(tokens);
25
    }
26

27
private:
28
    TreeNode* _build(std::queue<std::string>& tokens) {
29
        if (tokens.empty()) return nullptr;
30

31
        std::string val = tokens.front();
32
        tokens.pop();
33

34
        if (val == "null") return nullptr;
35

36
        TreeNode* node = new TreeNode(std::stoi(val));
37
        node->left = _build(tokens);
38
        node->right = _build(tokens);
39
        return node;
40
    }
41
};