public static void morrisIn(TreeNode root) {
if (root == null) return;
TreeNode cur = root;
TreeNode mostRight = null;
while (cur != null){
if (cur.left != null){
mostRight = cur.left;
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;
}
}
System.out.print(cur.val+" ");
cur = cur.right;
}
System.out.println();
}
public static void morrisPre(TreeNode root) {
if (root == null) return;
TreeNode cur = root;
TreeNode mostRight = null;
while (cur != null){
// 如果cur没有左孩子
if (cur.left != null){
mostRight = cur.left;
while (mostRight.right != null && mostRight.right != cur){
mostRight = mostRight.right;
}
// 由于 如果 mostRight.right == null 那么这里必然是没有左孩子的cur
if (mostRight.right == null){
System.out.print(cur.val+" ");
mostRight.right = cur;
cur = cur.left;
continue;
}else {
mostRight.right = null;
}
}else {
//cur有左孩子,那么必然会经历两次,在第一次来的时候就打印
System.out.print(cur.val+" ");
}
cur = cur.right;
}
}
原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。
如有侵权,请联系 cloudcommunity@tencent.com 删除。
原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。
如有侵权,请联系 cloudcommunity@tencent.com 删除。