看到除我以外的记录全是多少带个迭代器,指针变量什么的，深感心痛。 我这个大蒟蒻根本看不懂啊啊啊！ 并且，如果此题数据再增强一点变为1≤n≤1061 \le n \le 10^61≤n≤106的话，官方题解就挂了。 于是，今天，我就要写一篇无指针+O(n)代码，以让像我一样蒟蒻的人看懂代码！ 这边建树流程和官方一样，不过我把判定也写在里边了。 至于求值…… 当然是暴力查树啦 于是，代码也随之出现—— 时间复杂度： 建树最坏将每个点都遍历一次，为O(n)。 求值最坏也是将每个点都遍历一次，自然为O(n)。 最后，总复杂度便是O(n) 好像大家都省略了T…… 如果看到了本文，请评论，谢谢。 总之，希望这篇题解会对你理解题目有些关注。给个赞吧 bye~

题目解析 本题考查树的重构，根据二叉树的先序遍历和中序遍历，构建二叉树。 由于题目中给出的先序遍历和中序遍历不一定合法，所以我们首先思考，合法的先序遍历和中序遍历是什么样子的。 对于一个颗二叉树的先序遍历和中序遍历： 1. 令当前先序序列为 [preBegin,preEnd)[\tt{preBegin}, \tt{preEnd})[preBegin,preEnd)； 2. 令当前中序序列为 [inBegin,inEnd)[\tt{inBegin}, \tt{inEnd})[inBegin,inEnd)； 3. 当前先序序列的第一个元素即 preBegin\tt{preBegin}preBegin 上的元素，为当前子序列对应子树的根节点； 4. 在当前中序序列中找到根节点的位置 rootOfInOrd\tt{rootOfInOrd}rootOfInOrd，访问当前子树根节点； 5. 将当前中序序列以 rootOfInOrd\tt{rootOfInOrd}rootOfInOrd 分为左子树 [inBegin, rootOfInOrd)[\tt{inBegin},\ \tt{rootOfInOrd})[inBegin, rootOfInOrd) 和 右子树 [rootOfInOrd+1, inEnd)[\tt{rootOfInOrd+1},\ \tt{inEnd})[rootOfInOrd+1, inEnd) 两部分；同时可以获取左子树的大小 loLen=rootOfInOrd−inBegin\tt{loLen} = \tt{rootOfInOrd} - \tt{inBegin}loLen=rootOfInOrd−inBegin 和右子树的大小 hiLen=inEnd−(rootOfInOrd+1)\tt{hiLen} = \tt{inEnd} - \tt{(rootOfInOrd + 1)}hiLen=inEnd−(rootOfInOrd+1)； 6. 根据左子树的大小和右子树的大小，将先序序列分为左子树 [preBegin+1, preBegin+1+loLen)[\tt{preBegin+1},\ \tt{preBegin+1+loLen})[preBegin+1, preBegin+1+loLen) 和右子树 [preBegin+1+loLen, preEnd)[\tt{preBegin+1+loLen},\ \tt{preEnd})[preBegin+1+loLen, preEnd)； 7. 重复以上步骤，直至先序序列和中序序列为空。 上述过程中，若发现当前的先序序列中元素和中序序列中的元素不匹配则说明序列不合法。我们可以使用集合 std::set 来完成这个判断。 对于本题我们需要访问所有叶结点，并统计叶结点的深度信息。 那么在构建过程中，带着参数 depth\tt{depth}depth 记录这一信息即可。若发现当前先序序列和中序序列的大小为 111，则说明序列中元素为叶结点。在递归的过程中，递归获取左子树的叶结点深度之和 loSum\tt{loSum}loSum，右子树的叶结点深度之和 hiSum\tt{hiSum}hiSum，loSum+hiSum\tt{loSum + hiSum}loSum+hiSum 便是当前子树中所有叶结点深度之和。 AC代码 复杂度分析 根据先序遍历和中序遍历构建二叉树的过程中，朴素方法寻找根节点的总时间复杂度为 O(N2)\mathrm{O}(N^2)O(N2)； 判断先序序列中元素和中序序列中的元素是否匹配的时间复杂度为 O(Nlog⁡N)\mathrm{O}(N\log{N})O(NlogN)； 整个算法时间复杂度为 O(N2)\mathrm{O}(N^2)O(N2)。

思路一样，提供一种指针建树的写法。