二叉树的 Morris 前序和中序遍历 比较简单，而且基本结构非常相似，但是后序遍历相对更加困难，值得重点研究。
本题可以遵循后序遍历的正确顺序，通过指针的变化实现跳转，也可以采用逆向思维简化问题求解步骤。
常规解法的关键在于理解指针的变化方式到底会如何影响遍历的进程。假设二叉树的遍历过程中处在如下状态：
1
2
3
4
5
6
7
8
9
| /
a
/ \
b
/ \
c d
/ \
e f
curr -> a
|
按照中序遍历同样的方法构调整指针指向，会有如下过程：
- f.right -> a 即此时 prev = f
- curr -> b
- c.right -> b 即此时 prev = c
- curr -> c
- curr -> b
- c.right -> null
注意：因为有了步骤 3 的辅助指针调整，构造了一个环路，所以我们的 curr 指针在到达底层的 c 节点后，通过它的 right 指针又能回到 b。
按照后序遍历的定义左子树总是最先处理，那么 c 节点一定会先处理，但是可以先不理会它究竟具体在何处处理。但是，步骤 6 之后不可以马上处理 b 节点，而应该进入它的右子树 d 节点，以此类推处理了 e 节点之后会进入 f 节点。此时，可以通过 f.right 回到 a 节点（即 f 为 a 的 prev 指针），但是还有 b、d 和 f 节点未处理。而这 3 个节点可以通过 a.left 不断取 right 指针回到 a 节点，那么借助单链表反转的操作依次处理它们，这样的处理顺序也恰好符合后序遍历的定义。
另外，还应该注意到：curr -> b 时，反转 curr.left 到 prev 的链表并处理操作就是单独处理 c 节点（因为此时 c = b.left = prev）。这样，我们就把所有的节点处理操作统一为单链表反转操作。
这样，a 的左子树的遍历情况实际为如下顺序：
- c
- e
- f, d, b
非常像是用一条左上到右下的直线不断水平移动，直线和树的节点相重合时，就从下到上处理重合节点。
注意：
- 反转链表并处理节点之后，才能令 prev.right -> null，否则无法回到 curr 节点
- 反转链表并处理节点之后，记得再把链表反转会正常顺序，防止改变树的原有结构
最后，我们应该注意到上述处理方案实际最后并没有处理 a 节点，之后会进入 a 的右子树，只有当 curr 指向 a 的父节点时，才会通过反转链表的操作处理 a 节点。那么，我们就应该为整棵树的根构造一个假的父节点，使得假节点指向根节点，如此才能确保原来的树所有节点都被处理。当然，也不用担心假节点的内容会影响最后遍历结果，因为假节点无父节点而且右子树为 null，最后遍历进入它的右子树会停止。
我们不妨先求出后序遍历结果的反向序列，然后把结果反转即可得到正确的解。而反向序列的求解非常简单，就是参考前序遍历（中 -> 左 -> 右）的思路求解 中 -> 右 -> 左，只需要把 left 和 right 互换即可。
但是，这个解法实际上更像是投机取巧，毕竟完全有可能要求遍历时一次处理结果，而非将结果存入一个集合中，如果有这样的限制条件那么这个解法就不再可行。
解法二的伪码和代码都相对简单，可以参考前序完成，此处不再赘述，只记录解法一的伪代码。
解法一：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
| fun postorderTraversal(root: TreeNode?): List<Int> {
val dummy = TreeNode(0)
dummy.left = root
var curr: TreeNode? = dummy
val re = mutableListOf<Int>()
while (curr != null) {
if (curr.left == null) curr = curr.right
else {
var prev = curr.left!!
while (prev.right != null && prev.right != curr) prev = prev.right!!
if (prev.right == null) {
prev.right = curr
curr = curr.left
} else {
reverseProcess(curr.left!!, prev, re)
prev.right = null
curr = curr.right
}
}
}
return re
}
private fun reverseProcess(start: TreeNode, end: TreeNode, list: MutableList<Int>) {
reverseList(start, end)
var curr: TreeNode? = end
while (true) {
list.add(curr!!.`val`)
if (curr == start) break
curr = curr.right
}
reverseList(end, start)
}
private fun reverseList(start: TreeNode, end: TreeNode) {
if (start == end) return
var curr: TreeNode? = start.right
var prev: TreeNode = start
while (prev != end) {
val next = curr!!.right
curr.right = prev
prev = curr
curr = next
}
}
|
解法二：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| fun postorderTraversal(root: TreeNode?): List<Int> {
var curr = root
val re = ArrayList<Int>()
while (curr != null) {
if (curr.right == null) {
re.add(curr.`val`)
curr = curr.left
} else {
var prev = curr.right!!
while (prev.left != null && prev.left != curr) prev = prev.left!!
if (prev.left == null) {
prev.left = curr
re.add(curr.`val`)
curr = curr.right
} else {
prev.left = null
curr = curr.left
}
}
}
return re.asReversed()
}
|