Morris 遍历实现二叉树的遍历( 二 ) _生活百科

测评链接：LeetCode 94. Binary Tree Inorder Traversal
Morris遍历实现后序遍历Morris遍历实现后序遍历相对比较麻烦，处理时机只放在能回到自己两次的点，能回到自己两次的点在第二次回到自己的时刻，不打印它自己，而是逆序打印他左树的右边界, 整个遍历结束后，单独逆序打印整棵树的右边界，即得到了后序遍历的结果。
代码如下：
public List<Integer> postorderTraversal(TreeNode root) {if (root == null) {return new ArrayList<>();}List<Integer> ans = new ArrayList<>();TreeNode cur = root;TreeNode mostRight;while (cur != null) {mostRight = cur.left;if (mostRight != null) {while (mostRight.right != null && mostRight.right != cur) {mostRight = mostRight.right;}if (mostRight.right == null) {mostRight.right = cur;cur = cur.left;continue;} else {mostRight.right = null;// 第二次来到自己的时候，收集自己的左树的右边界collect(cur.left, ans);}}cur = cur.right;}collect(root, ans);return ans;}private void collect(TreeNode root, List<Integer> ans) {TreeNode node = reverse(root);TreeNode c = node;while (c != null) {ans.add(c.val);c = c.right;}reverse(node);}private TreeNode reverse(TreeNode node) {TreeNode pre = null;TreeNode cur = node;while (cur != null) {TreeNode t = cur.right;cur.right = pre;pre = cur;cur = t;}return pre;}需要注意两点：
第一点，collect方法即逆序收集左树的有边界，由于每个节点没有指向父的指针，所以，要实现逆序，需要针对右边界采用反转链表的方式。即reverse函数的逻辑。
第二点，在collect方法调用完反转链表操作后，还要还原整个右边界。否则整棵树的指针就指乱了。
测评链接：LeetCode 145. Binary Tree Postorder Traversal
更多算法和数据结构笔记
参考资料算法和数据结构体系班-左程云

Morris 遍历实现二叉树的遍历( 二 )

推荐阅读

汽车用品买什么是必备的买车以后有哪些重要的车用品

西梅可以冷冻保存吗怎么吃西梅可以冷冻保存吗

怎么自制减肥营养餐

立秋后的第一杯奶茶是什么意思?

快手小店上传商品审核多久快手商品审核多长时间

炒猪肚用什么配菜好吃炒猪肚用什么配菜

十二星座专属配套服装

关于感恩节的作文600字

人生自古谁无死出自哪首诗人生自古谁无死

2020年07月14日双子座事业爱情运势

绝地求生怎么跑绝地求生快速跑动按键详解

护士节的来历

依维柯宝迪edc灯消不掉怎么回事依维柯宝迪提示灯

请评教是什么意思网上评教是什么意思

机动车检验去哪里办理

冰箱里放三天的饭菜还可以吃吗饭菜放冰箱三天能吃吗

白城到长春白城到长春客车时间表

三国程普怎么死的

狮子座生日狮子座是几月份

好听的双胞胎男孩名字