晴问算法

记得在dfs那里给指针和数组加&，指针不加不会修改，数组不加会报错

#include <bits/stdc++.h>using namespace std;vector<int> preOrder, inOrder;
vector<int> result;struct TreeNode {int data;TreeNode *left;TreeNode *right;TreeNode(int data) : data(data), left(nullptr), right(nullptr) {}
};void dfs(TreeNode* &root, vector<int> &pre, vector<int> &in) {if (pre.empty()||in.empty()) return;int rootNum = pre[0];root = new TreeNode(rootNum);int root_Index;for (root_Index = 0; root_Index < in.size(); ++root_Index) {if (in[root_Index] == rootNum) break;}vector<int> vec1(pre.begin() + 1, pre.begin() + root_Index + 1);vector<int> vec2(pre.begin() + root_Index + 1, pre.end());vector<int> vec3(in.begin(), in.begin() + root_Index);vector<int> vec4(in.begin() + root_Index + 1, in.end());dfs(root->left, vec1, vec3);dfs(root->right, vec2, vec4);}void PostOrder(TreeNode *root) {if (root == nullptr) return;PostOrder(root->left);PostOrder(root->right);result.push_back(root->data);
}int main() {int n;cin >> n;for (int i = 0; i < n; ++i) {int num;cin >> num;preOrder.push_back(num);}for (int i = 0; i < n; ++i) {int num;cin >> num;inOrder.push_back(num);}TreeNode *root;dfs(root, preOrder, inOrder);PostOrder(root);for (int i = 0; i < result.size(); ++i) {if (i != 0) cout << " ";cout << result[i];}return 0;
}