时间复杂度O(N),空间复杂度O(1)的二叉树遍历
步骤:当前节点为current
1.若cur没有左孩子,cur向右移动(cur=cur.right)
2.若cur有左孩子,找到cur左孩子左子树上最右的节点,记为mostright
1)若mostright的右指针指向空,让其指向cur,cur向左移动
2)若mostright的右指针指向cur,让其指向空,cur向右移动
二叉树.png
如图所示的二叉树的遍历顺序为:
124
251
36
37
所有有左子树的节点都会遍历两次
前序遍历:第一次经过节点时打印
中序遍历:最后一次经过节点时打印
后序遍历:只关注能够两次遍历的节点,在第二次到达节点时打印其左子树的右边界(4526)
最后单独打印整棵树的右边界
public void inOrderByMorris(TreeNode root) {
TreeNode curr = root;
while (curr != null) {
if (curr.left == null) {//步骤1
System.out.print(curr.val + " ");
curr = curr.right;
} else {//步骤2
TreeNode predecessor = getPredecessor(curr);
if (predecessor.right == null) {//步骤2.a
predecessor.right = curr;
curr = curr.left;
} else if (predecessor.right == curr) {//步驟2.b
predecessor.right = null;
System.out.print(curr + " ");
curr = curr.right;//这段的右孩子,其实是我们人为设置的
}
}
}
}
private TreeNode getPredecessor(TreeNode curr) {
TreeNode predecessor = curr;
if (curr.left != null) {
predecessor = curr.left;
while (predecessor.right != null && predecessor.right != curr) {
predecessor = predecessor.right;
}
}
return predecessor;
}
作者:a-fei-8
链接:https://leetcode-cn.com/problems/recover-binary-search-tree/solution/yi-wen-zhang-wo-morrisbian-li-suan-fa-by-a-fei-8/
来源:力扣(LeetCode)
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。
leetcode99.恢复二叉树
image.png
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public void recoverTree(TreeNode root) {
TreeNode before = null;
TreeNode t1 = null;
TreeNode t2 = null;
TreeNode curr = root;
while (curr != null) {
if (curr.left != null) {
TreeNode predecessor = getPredecessor(curr);
if (predecessor.right == null) {
predecessor.right = curr;
curr = curr.left;
continue;
} else if (predecessor.right == curr) {
predecessor.right = null;
}
}
if(before != null && t1==null && before.val > curr.val ){
t1 = before;
}
if(before != null && t1!=null && before.val > curr.val ){
t2 = curr;
}
before = curr;
curr = curr.right;
}
swap(t1,t2);
}
private TreeNode getPredecessor(TreeNode curr) {
TreeNode predecessor = curr;
if (curr.left != null) {
predecessor = curr.left;
while (predecessor.right != null && predecessor.right != curr) {
predecessor = predecessor.right;
}
}
return predecessor;
}
private void swap(TreeNode first, TreeNode second) {
if (first != null && second != null) {
int temp = first.val;
first.val = second.val;
second.val = temp;
}
}
}