220510二叉树遍历-前序-morris

public class TreeNode {
    public int val;
    public TreeNode left;
    public TreeNode right;
    public int deep;
    public TreeNode(){}
    public TreeNode(int val) {this.val = val;}
    public TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

public static void main(String[] args) {
        TreeNode node7 = new TreeNode(7, null, null);
        TreeNode node6 = new TreeNode(6, null, null);
        TreeNode node5 = new TreeNode(5, node6, node7);
        TreeNode node4 = new TreeNode(4, null, null);
        TreeNode node3 = new TreeNode(3, null, null);
        TreeNode node2 = new TreeNode(2, node4, node5);
        TreeNode node1 = new TreeNode(1, node2, node3);
        morrisPre(node1);
    }

    /**
     * 实现时间复杂度为O(N)，而空间复杂度为O(1)的精妙算法
     * @param cur
     */
    private static void morrisPre(TreeNode cur) {
        if (null == cur) {
            return;
        }
        TreeNode mostRight = null;
        while (null != cur) {
            // cur表示当前节点，mostRight表示cur的左孩子的最右节点
            mostRight = cur.left;
            // 当左节点不为空时，找到左节点最右边的节点
            if (null != mostRight ) {
                // cur有左孩子，找到cur左子树最右节点
                while (mostRight.right !=null && mostRight.right != cur){
                    mostRight = mostRight.right;
                }
                // mostRight的右孩子指向空，让其指向cur，cur向左移动
                if (mostRight.right == null){ // 建立线索指针
                    mostRight.right = cur;
                    System.out.println(cur.val);
                    cur = cur.left;
                    continue;
                } else { // 删除线索指针
                    mostRight.right = null;
                }
            } else {
                System.out.println(cur.val);
            }
            cur = cur.right;
        }

    }