1回答

liuyubobobo

2018-07-04

已采纳

如果你已经学习了二叉树的前序遍历的非递归代码，仔细观察，其实这个代码就是一个“反向”的前序遍历代码。所谓的“反向”，是指对于每个节点，先找右子树，再找左子树：）

这样进行“反向”的前序遍历，最终得到的遍历结果（存储在了output中），再反转过来，就是后序遍历的结果：）这个翻转过程表现在最后的while循环中，output的元素是从后向前输出的（使用pop）：）

0

4

liuyubobobo

回复

丶远走高飞

首先，先将这段代码的left换成right，right换成left，仔细观察（或者模拟，调试）一下，看看是不是就编程前序遍历了？明确一下，这段代码就是我所说的“反向前序遍历”。 之后，关键就变成了，为什么反向前序遍历的结果等于后续遍历？可以借助课程中所讲的每个节点有三个访问点来思考。前序遍历是按照左中右的顺序先左子树后右子树的访问每一个节点；“反向前序遍历”是右中左的顺序先右子树后左子树的访问每个节点。它和前序遍历是左右对称的！：）

2018-07-04

共4条回复