首页 > 代码库 > morris Traversal
morris Traversal
O(n)时间，O(1)空间对二叉树进行前序、中序、后序遍历。详细讲解看参考。
public class Solution { public static void morrisPreorder(TreeNode root) { TreeNode cur = root; TreeNode pre = null; while (cur != null) { if (cur.left == null) { System.out.print(cur.val + " "); cur = cur.right; } else { // find predecessor pre = cur.left; while (pre.right != null && pre.right != cur) pre = pre.right; if (pre.right == null) { System.out.print(cur.val + " "); pre.right = cur; cur = cur.left; } else { pre.right = null; cur = cur.right; } } } System.out.println(); } public static void morrisInorder(TreeNode root) { TreeNode cur = root; TreeNode pre = null; while (cur != null) { if (cur.left == null) { System.out.print(cur.val + " "); cur = cur.right; } else { // find predecessor pre = cur.left; while (pre.right != null && pre.right != cur) pre = pre.right; if (pre.right == null) { pre.right = cur; cur = cur.left; } else { pre.right = null; System.out.print(cur.val + " "); cur = cur.right; } } } System.out.println(); } public static void morrisPostorder(TreeNode root) { TreeNode dump = new TreeNode(0); dump.left = root; TreeNode cur = dump; TreeNode pre = null; while (cur != null) { if (cur.left == null) { cur = cur.right; } else { // find predecessor pre = cur.left; while (pre.right != null && pre.right != cur) pre = pre.right; if (pre.right == null) { pre.right = cur; cur = cur.left; } else { pre.right = null; printRev(cur.left, pre); cur = cur.right; } } } System.out.println(); } private static void printRev(TreeNode from, TreeNode to) { reverse(from, to); TreeNode p = to; while (true) { System.out.print(p.val + " "); if (p == from) break; p = p.right; } reverse(to, from); } private static void reverse(TreeNode from, TreeNode to) { if (from == to) return; TreeNode pre = from, cur = from.right, post = null; while (pre != to) { post = cur.right; cur.right = pre; pre = cur; cur = post; } } public static void main(String[] args) { String s = "6 2 1 # # 4 3 # # 5 # # 7 # 9 # 8 # #"; TreeNode root = TreeUtils.makeTree(s); TreeUtils.printTree(root); morrisPreorder(root); morrisInorder(root); morrisPostorder(root); }}
复杂度分析：
空间复杂度：O(1)，因为只用了两个辅助指针。
时间复杂度：O(n)。证明时间复杂度为O(n)，最大的疑惑在于寻找中序遍历下二叉树中所有节点的前驱节点的时间复杂度是多少，即以下两行代码：
while (pre.right != null && pre.right != cur) pre = pre.right;
直觉上，认为它的复杂度是O(nlgn)，因为找单个节点的前驱节点与树的高度有关。但事实上，寻找所有节点的前驱节点只需要O(n)时间。n个节点的二叉树中一共有n-1条边，整个过程中每条边最多只走2次，一次是为了定位到某个节点，另一次是为了寻找上面某个节点的前驱节点，如下图所示，其中红色是为了定位到某个节点，黑色线是为了找到前驱节点。所以复杂度为O(n)。
参考（讲的太好了）：
http://www.cnblogs.com/AnnieKim/archive/2013/06/15/MorrisTraversal.html
morris Traversal
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。