Morris遍历

时间复杂度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;
        }
    }
}
最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容