@[xixi_bang](/user/322896)
我生成了一组数据如下：
```
239 295 312 333 313 303 254 178 147 100 175 242 280 183 109 151 72 99 75 179 226 111 302 121 73 45 311 297 213 113 95 186 155 171 10 255 24 293 93 231 140 163 135 238 263 274 262 202 30 279 304 249 117 170 191 207 128 23 157 40 173 5 33 265 316 91 326 43 187 240 102 306 286 292 184 96 114 196 224 131 322 331 210 203 123 166 321 167 146 251 289 90 64 192 253 198 217 221 88 327 328 298 89 57 87 153 334 309 276 294 315 193 260 190 58 106 97 83 142 39 222 2 69 132 144 165 199 267 212 330 22 8 208 149 84 53 138 42 154 278 103 21 107 233 197 215 273 329 307 281 32 15 94 46 194 112 101 66 12 122 82 319 50 299 284 172 268 77 76 214 104 1 116 108 336 68 51 120 105 148 7 129 211 277 181 188 244 141 119 65 80 174 230 257 317 220 290 85 55 70 92 6 301 127 63 44 152 248 250 236 288 185 13 3 37 62 256 4 241 176 225 332 16 136 164 47 156 14 52 252 9 35 287 335 48 125 247 137 59 81 180 325 25 60 228 275 150 161 300 110 133 115 27 324 18 200 320 31 61 234 209 216 219 26 204 201 258 124 160 223 139 19 323 182 243 246 227 229 17 79 218 158 168 282 272 245 237 189 34 98 118 56 49 318 145 28 205 134 259 159 126 310 67 162 261 78 308 270 38 130 235 20 264 269 271 314 291 54 195 305 283 232 296 11 41 266 86 169 143 29 177 337 74 285 36 71 206
239 295 303 313 254 333 178 100 147 280 242 175 109 151 75 99 179 111 302 226 45 311 73 213 113 95 186 171 24 255 10 293 231 140 93 163 238 263 274 135 155 297 121 72 183 202 30 304 249 279 262 312 170 207 128 23 40 157 191 265 33 5 326 43 91 187 316 173 240 117 286 306 184 114 196 131 322 224 210 203 331 96 292 321 166 146 251 90 64 192 289 253 167 217 221 328 57 89 298 153 87 309 276 334 327 58 190 260 193 97 83 106 315 222 39 142 294 88 198 132 69 165 199 144 330 22 212 149 208 8 267 42 138 154 53 21 107 103 278 84 2 197 273 307 329 281 32 215 94 194 112 46 101 15 233 123 102 122 82 12 299 77 268 76 172 284 50 319 104 1 108 51 120 105 148 68 336 116 277 211 129 188 244 181 7 214 65 119 174 80 257 230 290 220 70 55 85 6 44 248 152 236 288 185 250 63 127 301 3 256 62 37 13 92 241 176 332 136 164 16 14 52 156 47 225 9 252 335 48 247 125 137 287 180 25 325 275 228 60 81 59 110 133 300 324 27 115 200 18 161 31 320 234 209 61 150 219 204 26 216 35 4 317 258 124 223 19 139 160 243 182 246 229 227 79 168 272 282 245 237 34 189 158 56 145 318 49 118 98 259 126 310 67 159 134 261 162 270 308 38 78 205 28 218 17 235 264 271 269 54 291 305 232 296 283 195 314 11 266 86 41 20 143 169 177 36 285 206 71 74 337 29 130 323 201 141 66
```
正确的输出应该是104，而您的代码输出的结果是94，解题逻辑尚存在错误。
本题需要通过中序遍历和后序遍历的结果将树还原出来，然后过一趟从根结点开始的DFS过程即可确定结果。关键点在于树的恢复。如果树的恢复发生错误，结果难免发生错误。
另外您用拆分的方式读取输入，这样似乎有些繁琐，可以直接考虑使用istringstream进行读入更为简便。例如：
```cpp
string inorder, postorder;
while (getline(cin, inorder), getline(cin, postorder))
{
// in存储中序遍历的结果，post存储后续遍历的结果。
vector<int> in, post;
int number;
istringstream iss(inorder);
while (iss >> number)
in.push_back(number);
iss.clear();
iss.str(postorder);
while (iss >> number)
post.push_back(number);
// 后续处理...
}
```
您能够较为详细的解释一下您的解题逻辑吗？这样有助于您理清解题思路以便发现错误。
by metaphysis @ 2020-03-29 21:53:27
@[xixi_bang](/user/322896)
测试数据粘贴上去格式好像错误了，如果您需要的话，我私信发给您。
by metaphysis @ 2020-03-29 21:56:04
@[metaphysis](/user/333388) 您好，谢谢您的解答，我的解答思路如下：（1）getn函数用于将读入的字符切分进int数组 (2)built函数用于建树，根据后序以及中序遍历结果递归建树：当前后序遍历最后一个元素为要建立的结点（可以理解为当前的根结点），在中序序列中查找该根节点，即可划分出左子树以及右子树，再对左子树右子树来递归建立（同上的过程） （3）dfs深度优先遍历树，从根节点开始遍历起，直到遇到叶子结点即停止，遍历过程中记录遇到的结点的编号之和，记录了一个minn最小值，若小于该最小值，即更新最小值
by xixi_bang @ 2020-03-30 20:13:27
@[metaphysis](/user/333388) 您好，能麻烦您给我发一份测试数据吗~
by xixi_bang @ 2020-03-30 20:39:38
@[xixi_bang](/user/322896)
```
239 295 312 333 313 303 254 178 147 100 175 242
280 183 109 151 72 99 75 179 226 111 302 121 73
45 311 297 213 113 95 186 155 171 10 255 24 293
93 231 140 163 135 238 263 274 262 202 30 279
304 249 117 170 191 207 128 23 157 40 173 5
33 265 316 91 326 43 187 240 102 306 286 292
184 96 114 196 224 131 322 331 210 203 123
166 321 167 146 251 289 90 64 192 253 198
217 221 88 327 328 298 89 57 87 153 334 309
276 294 315 193 260 190 58 106 97 83 142 39
222 2 69 132 144 165 199 267 212 330 22 8 208
149 84 53 138 42 154 278 103 21 107 233 197
215 273 329 307 281 32 15 94 46 194 112 101
66 12 122 82 319 50 299 284 172 268 77 76
214 104 1 116 108 336 68 51 120 105 148 7
129 211 277 181 188 244 141 119 65 80 174
230 257 317 220 290 85 55 70 92 6 301 127
63 44 152 248 250 236 288 185 13 3 37 62
256 4 241 176 225 332 16 136 164 47 156
14 52 252 9 35 287 335 48 125 247 137 59
81 180 325 25 60 228 275 150 161 300 110
133 115 27 324 18 200 320 31 61 234 209 216
219 26 204 201 258 124 160 223 139 19 323 182
243 246 227 229 17 79 218 158 168 282 272 245
237 189 34 98 118 56 49 318 145 28 205 134 259
159 126 310 67 162 261 78 308 270 38 130 235 20
264 269 271 314 291 54 195 305 283 232 296 11 41
266 86 169 143 29 177 337 74 285 36 71 206
-------
239 295 303 313 254 333 178 100 147 280 242
175 109 151 75 99 179 111 302 226 45 311 73
213 113 95 186 171 24 255 10 293 231 140 93
163 238 263 274 135 155 297 121 72 183 202
30 304 249 279 262 312 170 207 128 23 40 157
191 265 33 5 326 43 91 187 316 173 240 117
286 306 184 114 196 131 322 224 210 203 331
96 292 321 166 146 251 90 64 192 289 253 167
217 221 328 57 89 298 153 87 309 276 334 327
58 190 260 193 97 83 106 315 222 39 142 294
88 198 132 69 165 199 144 330 22 212 149 208
8 267 42 138 154 53 21 107 103 278 84 2 197
273 307 329 281 32 215 94 194 112 46 101 15
233 123 102 122 82 12 299 77 268 76 172 284
50 319 104 1 108 51 120 105 148 68 336 116
277 211 129 188 244 181 7 214 65 119 174 80
257 230 290 220 70 55 85 6 44 248 152 236
288 185 250 63 127 301 3 256 62 37 13 92
241 176 332 136 164 16 14 52 156 47 225 9
252 335 48 247 125 137 287 180 25 325 275
228 60 81 59 110 133 300 324 27 115 200 18
161 31 320 234 209 61 150 219 204 26 216 35
4 317 258 124 223 19 139 160 243 182 246 229
227 79 168 272 282 245 237 34 189 158 56 145
318 49 118 98 259 126 310 67 159 134 261 162
270 308 38 78 205 28 218 17 235 264 271 269
54 291 305 232 296 283 195 314 11 266 86 41
20 143 169 177 36 285 206 71 74 337 29 130
323 201 141 66
```
by metaphysis @ 2020-03-30 21:27:59
分割线上面是中序遍历结果，下面是后序遍历结果。您稍微处理一下，把中序和后序各放在一行上即可。
by metaphysis @ 2020-03-30 21:29:06
@[xixi_bang](/user/322896)
看了您的解题思路，再结合您的代码，我大概知道问题在哪里了。
原题中输出时的要求为：
```
For each tree description you should output the value of the leaf node of a path of least value. In the case of multiple paths of least value you should pick the one with the least value on the terminal node.
```
即当多条路径具有最小的路径和时，取叶结点的最小值。而您的代码：
```
if(ans<=minn&&(T->data)<leaf) {//按字典序输出
leaf=(T->data);
minn=ans;
}
```
不能达到此要求，应该需要将其更改为：
```cpp
if (ans < minn || (ans == minn && (T->data) < leaf)) {
leaf = (T->data);
minn = ans;
}
```
by metaphysis @ 2020-03-30 21:42:46
@[metaphysis](/user/333388) 谢谢您的耐心解答~问题已解决~
by xixi_bang @ 2020-03-31 21:19:27