Given a binary tree, return the postorder traversal of its nodes' values.
Morris Traversal
Morris Traversal
后续遍历稍显复杂，需要建立一个临时节点dump，令其左孩子是root。并且还需要一个子过程，就是倒序输出某两个节点之间路径上的各个节点。
步骤：
当前节点设置为临时节点dump。
1. 如果当前节点的左孩子为空，则将其右孩子作为当前节点。
2. 如果当前节点的左孩子不为空，在当前节点的左子树中找到当前节点在中序遍历下的前驱节点。
a) 如果前驱节点的右孩子为空，将它的右孩子设置为当前节点。当前节点更新为当前节点的左孩子。
b) 如果前驱节点的右孩子为当前节点，将它的右孩子重新设为空。倒序输出从当前节点的左孩子到该前驱节点这条路径上的所有节点。当前节点更新为当前节点的右孩子。
3. 重复以上1、2直到当前节点为空。
public ArrayList<Integer> postorderTraversal(TreeNode root) {
ArrayList<Integer> result = new ArrayList<Integer>();
TreeNode dummy = new TreeNode(0);
dummy.left = root;
TreeNode p = dummy, q = null;
while (p != null) {
if (p.left == null) {
p = p.right;
} else {
// Find in-order predecessor of current node
q = p.left;
while (q.right != null && q.right != p)
q = q.right;
if (q.right == null) { // Its left subtree has not been traversed; link it to its predecessor
q.right = p;
p = p.left;
} else {
// Its left subtree has been traversed; add the numbers from p's left child to its in-order
// predecessor in reverse order, and recover tree structure
reverse(p.left, q);
TreeNode temp = q;
while (temp != p.left) {
result.add(temp.val);
temp = temp.right;
}
result.add(temp.val);
reverse(q, p.left);
q.right = null;
p = p.right;
}
}
}
return result;
}
private void reverse(TreeNode from, TreeNode to) {
if (from == to)
return;
TreeNode q = from, p = from.right;
while (q != to) {
TreeNode next = p.right;
p.right = q;
q = p;
p = next;
}
}
Read full article from LeetCode - Binary Tree Postorder Traversal | Darren's Blog