关于用遍历结果确定树的时间复杂度

学术版

liruizhou_lihui @ 2024-11-28 23:01:47

比如给定前序遍历和中序遍历，如果以枚举根节点左右递归建树然后树建好之后求前序遍历判断是否一致。

这种找法时间复杂度是多少，如果节点数量是 n ,时间复杂度是 \text{O}(n! \times n) 吗

by litjohn @ 2024-11-28 23:08:36

@liruizhou_lihui 为什么要再次求前序遍历？不求的话是 O(n^2)

by Joe2011 @ 2024-11-28 23:19:12

@liruizhou_lihui 为什么要枚举根节点啊？前序遍历第一个不就是根吗？？？

不枚举可以做到 O(n\log n)

by Joe2011 @ 2024-11-28 23:20:20

@liruizhou_lihui 搞错了，是 O(n^2)

极限数据：链

|