013-二叉链表的遍历

使用线索二叉树的方式来对二叉链表进行遍历操作

//       线索二叉树
//    时间复杂度为o(n) 使用空闲指针来解决空间复杂度
//    morris实现遍历 前序遍历
    public static void morrisPre(TreeNode cur)
    {
        if(cur == null)return;
        //最右边的节点
        TreeNode mostRright = null;
        while(cur!=null) {
            mostRright = cur.left;
            if(mostRright!=null)
            {
                //在它在左子树中找最右节点 直到找到前驱节点
                while (mostRright.right != null && mostRright != cur) {
                    mostRright = mostRright.right;
                }
                //找到的前驱节点就是null 维护指针
                if (mostRright.right == null)
                {
                    mostRright.right = cur;
                    //在移动之前将自己的值进行打印
                    System.out.println(cur.val);
                    //在继续找最左边的指针
                    cur = cur.left;
                    continue;
                }
                else
                {
//                mostRright.right ==cur 删除线索指针
                    mostRright.right = null;
                }
            }
            else
            {
                //找到了最左边的节点 需要将这个值进行打印
                System.out.println(cur.val);
            }
            //找右子树
            cur = cur.right;
        }
    }

public static void morrisMid(TreeNode cur)
    {
        if(cur == null)return;
        //最右边的节点
        TreeNode mostRright = null;
        while(cur!=null) {
            mostRright = cur.left;
            if(mostRright!=null)
            {
                //在它在左子树中找最右节点 直到找到前驱节点
                while (mostRright.right != null && mostRright != cur) {
                    mostRright = mostRright.right;
                }
                //找到的前驱节点就是null 维护指针
                if (mostRright.right == null)
                {
                    mostRright.right = cur;
                    //在继续找最左边的指针
                    cur = cur.left;
                    continue;
                }
                else
                {
//                mostRright.right ==cur 删除线索指针
                    mostRright.right = null;
                }
            }
            //打印最左边的语句
            System.out.println(cur.val);
            //找右子树
            cur = cur.right;
        }
    }

 public static void morrisPost(TreeNode cur)
    {
        if(cur == null)return;
        //最右边的节点
        TreeNode mostRright = null;
        while(cur!=null) {
            mostRright = cur.left;
            if(mostRright!=null)
            {
                //在它在左子树中找最右节点 直到找到前驱节点
                while (mostRright.right != null && mostRright != cur) {
                    mostRright = mostRright.right;
                }
                //找到的前驱节点就是null 维护指针
                if (mostRright.right == null)
                {
                    mostRright.right = cur;

                    //在继续找最左边的指针
                    cur = cur.left;
                    continue;
                }
                else
                {
//                mostRright.right ==cur 删除线索指针
                    mostRright.right = null;
                    printNode(cur.left);
                }
            }

            //找右子树
            cur = cur.right;
        }
    }
    public static void printNode(TreeNode head)
    {
        TreeNode tail = reverse(head);
        while(tail!=null)
        {
            System.out.println(tail.val);
            tail = tail.right;
        }
        reverse(tail);
    }
    public static TreeNode reverse(TreeNode head)
    {
        TreeNode prev = null,cur = head,next;
        while(cur!=null)
        {
            next = cur.right;
            cur.right = prev;
            prev = cur;
            cur = next;
        }
        return prev;
    }