图后序遍历与前序遍历

Question

图的后序遍历不是前序遍历的逆向吗？如果不是的话这两个遍历什么关系

Answer 1

liuyubobobo 2020-12-28 09:48:05

不是。从树的遍历都可以看出来。（树是特殊的图）

  1
 / \
2   3

从 1 开始，前序遍历的结果是 1, 2, 3

后续遍历的结果是 2, 3, 1

所以我们需要单独做后序遍历，而不是把前序遍历的结果逆过来就是后序遍历。

二者的关系就是二者的定义：

前序遍历是先遍历顶点，再遍历这个顶点的所有没有遍历过偶的后续节点；

后序遍历是在遍历完一个节点的所有后续节点以后，再遍历这个节点。

继续加油！：）