tree
常数空间Invert Binary Tree与仿Morris法后序遍历
今天在地铁上浪费了好多时间……呜呜……做其他事都没有效率，就利用这些时间写字了。
前几天LeetCode的Invert Binary Tree火了。名称有点糟，无法准确描述要求。
主要思路是遍历二叉树，把访问操作修改为交换左右孩子，每个节点都交换一次即可。
如果采用前序或中序遍历，则子树交换发生在遍历某棵子树之前，会引起麻烦。因此我想到了后序遍历，在遍历完子树后再交换左右孩子，重心就是如何实现常数空间复杂度的后序遍历。某些资料/问题称之为Morris post-order traversal。
…二叉树遍历算法总结
三类：
- 栈
- 系统栈
- 自己实现的栈
- 线索：Morris preorder/inorder/postorder traversal
- 其他edge-crawling方式：Schorr-Waite graph marking algorithm、Lindstrom-Dwyer algorithm