二叉树非递归后序遍历
1. Using 1 stack
O(n) time, O(n) space
初始设置栈为空，当前节点为根节点
执行以下操作，直到栈为空且当前节点为空时停止：
- 当前节点入栈，将左孩子设为当前节点，直到当前节点为空。
- 令当前节点为stack[-1]
- 如果当前节点右孩子为空，或等于prev（说明已经访问过右子树）
– 访问当前节点，出栈
– 设置prev=当前节点
– 令当前节点=None - 否则，将右孩子设为当前节点
stack = []
node = root
while node and stack:
if node:
stack.append(node)
node = node.left
else:
node = stack[-1]
if not node.right or node.right == prev:
print(node.val)
stack.pop()
node = None
else:
node = node.right
2. Using 2 stacks
O(n) time, O(n) space
stack: 用于储存和遍历子节点，初始化=[root]
path: 记录从根节点到当前节点的路径
执行以下操作，直到stack为空：
- node = stack[-1]
- 如果path栈顶元素不是node：
– 当前节点，右孩子，左孩子（如果非空），依次入栈stack - 如果stack和path栈顶元素相同：
– 访问node
– stack和path弹出栈顶
stack = [root]
path = []
while stack:
node = stack.pop()
if path and path[-1] == node:
path.pop()
print(node.val)
else:
path.append(node)
if node.right: stack.append(node.right)
stack.append(node)
if node.left: stack.append(node.left)
3. Using no stacks (Morris traversal)
O(n) time, O(1) space
在中序morris traversal的基础上作修改，遍历顺序由 “左根右” 变为 “左右根”。一种方法是添加dummy节点使得根节点为其左孩子，然后使用reverse辅助函数将每一层 “根到最右” 的部分反转，遍历该层之后再反转恢复结构。图片来源是leetcode用户xruzty的这篇文章。
新建dummy节点，设置其左孩子为root
初始化node = dummy
进行以下操作直到node为空：
- 如果当前节点node的左孩子非空，找到中序遍历的前驱节点，左孩子的最右后代
– 如果前驱节点的右孩子为空，将前驱节点的右孩子设置为当前节点。更新 node = node.left
– 如果前驱节点的右孩子非空（则为当前节点；说明在上行过程中，前驱节点之前的层已被访问过）：- 反转node.left至prev这一层
- 遍历访问prev至node.left
- 再次反转恢复原结构
- 恢复树结构：prev.right = None
- node = node.right
- 如果node的左孩子为空，更新 node = node.right
def reverse(start, end):
if start == end:
return
prev = start
node = start.right
while prev != to:
tmp = node.right
node.right = prev
prev = node
node = tmp
dummy = TreeNode(None)
dummy.left = root
node = dummy
while node and node.val:
if node.left:
prev = node.left
while prev.right and prev.right != node:
prev = prev.right
if not prev.right:
prev.right = node
node = node.left
else:
reverse(node.left, prev)
tmp = prev
while tmp != node.left:
print(tmp.val)
tmp = tmp.right
print(tmp.val) # print node.left.val
prev.right = None
node = node.right
else:
node = node.right