树递归遍历和Mirrors遍历

树的前序遍历

给你二叉树的根节点 root ，返回它节点值的 前序 遍历
前序遍历就是按照根节点-左节点-右节点的顺序完成遍历，他的每一颗子树都遵循这个遍历的顺序，就称为前序遍历

    ArrayList<Integer> list = new ArrayList<Integer>();
    public List<Integer> preorderTraversal(TreeNode root) {
        if(root == null) return list;
        list.add(root.val);
        preorderTraversal(root.left);
        preorderTraversal(root.right);
        return list;
    }
==========================抽取出前序递归的方法============================
    public List<Integer> preorderTraversal(TreeNode root) {
        ArrayList<Integer> list = new ArrayList<Integer>();
        preorder(root,list);
        return list;
    }
    private void preorder(TreeNode root,List<Integer> res){
        if(root == null){
            return;
        }
        res.add(root.val);
        preorder(root.left,res);
        preorder(root.right,res);
    }

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

树的中序遍历

按照每一棵树的左节点-根节点-右节点顺序遍历的结果

    public List<Integer> inorderTraversal(TreeNode root) {
        ArrayList<Integer> list = new ArrayList<Integer>();
        search(root,list);
        return list;
    }

    private void search(TreeNode node,ArrayList<Integer> list){
        if (node == null){return;}
        search(node.left,list);
        list.add(node.val);
        search(node.right,list);
    }
1
2
3
4
5
6
7
8
9
10
11
12

树的后序遍历

按照每一棵树的左节点-右节点-根节点顺序遍历的结果

    public List<Integer> postorderTraversal(TreeNode root) {
        ArrayList<Integer> list = new ArrayList<Integer>();
        postorder(root,list);
        return list;
    }

    private void postorder(TreeNode root,List<Integer> list){
        if(root == null) return;
        postorder(root.left,list);
        postorder(root.right,list);
        list.add(root.val);
    }
1
2
3
4
5
6
7
8
9
10
11
12

树的层序遍历

广度优先搜索，树的每一层进行遍历【从左到右，从上而下】
维护了一个队列queue，队列的长度就是树的每一层节点的个数

	public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> res = new ArrayList<List<Integer>>();
        if(root == null) return res;
        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        queue.offer(root);
        while(!queue.isEmpty()){
            List<Integer> level = new ArrayList<Integer>();
            int curLevelSize = queue.size();
            for(int i = 1; i <= curLevelSize; i++){
                TreeNode node = queue.poll();
                level.add(node.val);
                if(node.left != null){
                    queue.offer(node.left);
                }
                if(node.right != null){
                    queue.offer(node.right);
                }
            }
            res.add(level);
        }
        return res;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

Mirrors

Morris遍历使用二叉树节点中大量指向null的指针，由Joseph Morris 于1979年发明。
时间复杂度：O(n)
额外空间复杂度：O(1)
算法实现：当前的cur，一开始cur到达整棵树的根部

• cur无左树，cur = cur.right;
• cur有左树，找到左树的最右节点mostRight
  • mostRight的右指针指向null，mostRight.right = cur;cur = cur.left;
  • mostRight的右指针指向cur，mostRight.right = null;cur = cur.right;

Mirrors的遍历
按照算法，不断的找到左树的最右节点的右指针为null，直指向cur，右指针是当前节点，就恢复null，cur右移动。

    public void mirrorsOrder(TreeNode root) {
        if(root == null) return;
        TreeNode cur = root;
        TreeNode mostRight = null;
        while(cur != null){
            mostRight = cur.left;
            // 没有左树，cur就往右移动
            if(mostRight != null){
                // 左树的最右节点
                while(mostRight.right != null && mostRight.right != cur){
                    mostRight = mostRight.right;
                }
                // 左树的最右节点为null，指向cur，cur往左移动
                if(mostRight.right == null){
                    mostRight.right = cur;
                    cur = cur.left;
                    continue;
                }else{
           			// 指向cur，左树的最右节点指向null，最后跳出if，cur右移
                    mostRight.right = null;
                }
                
            }
            cur = cur.right;
        }
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

前序遍历
打印创建最右节点的右指针的时候打印cur和自身无法创建连线的节点也就是叶子节点

public static void preOrderMorris(TreeNode head) {
	if (head == null) {
		return;
	}
	TreeNode cur1 = head;
	TreeNode cur2 = null;
	while (cur1 != null) {
		cur2 = cur1.left;
		if (cur2 != null) {
			while (cur2.right != null && cur2.right != cur1) {
				cur2 = cur2.right;
			}
			if (cur2.right == null) {
				cur2.right = cur1;
				System.out.print(cur1.value + " ");
				cur1 = cur1.left;
				continue;
			} else {
				cur2.right = null;
			}
		} else {
			System.out.print(cur1.value + " ");
		}
		cur1 = cur1.right;
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

中序遍历
从最左侧开始顺着右节点打印。也就是在将cur1切换到上层节点的时候。
就是mirrors序的cur1遍历的节点出现一次或者两次【左树最右节点回去】两次的在第二次打印即可

public static void inOrderMorris(TreeNode head) {
	if (head == null) {
		return;
	}
	TreeNode cur1 = head;
	TreeNode cur2 = null;
	while (cur1 != null) {
		cur2 = cur1.left;
		//构建连接线
		if (cur2 != null) {
			while (cur2.right != null && cur2.right != cur1) {
				cur2 = cur2.right;
			}
			if (cur2.right == null) {
				cur2.right = cur1;
				cur1 = cur1.left;
				continue;
			} else {
				cur2.right = null;
			}
		}
		System.out.print(cur1.value + " ");
		cur1 = cur1.right;
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

后序遍历
反向打印节点的右边+根节点的右边

打印的应该是 4 5 2 6 7 3 1

//后序Morris
public static void postOrderMorris(TreeNode head) {
	if (head == null) {
		return;
	}
	TreeNode cur1 = head;//遍历树的指针变量
	TreeNode cur2 = null;//当前子树的最右节点
	while (cur1 != null) {
		cur2 = cur1.left;
		if (cur2 != null) {
			while (cur2.right != null && cur2.right != cur1) {
				cur2 = cur2.right;
			}
			if (cur2.right == null) {
				cur2.right = cur1;
				cur1 = cur1.left;
				continue;
			} else {
				cur2.right = null;
				// 打印节点的右边
				postMorrisPrint(cur1.left);
			}
		}
		cur1 = cur1.right;
	}
	postMorrisPrint(head);
}
//打印函数
public static void postMorrisPrint(TreeNode head) {
	TreeNode reverseList = postMorrisReverseList(head);
	TreeNode cur = reverseList;
	while (cur != null) {
		System.out.print(cur.value + " ");
		cur = cur.right;
	}
	postMorrisReverseList(reverseList);
}
//翻转单链表
public static TreeNode postMorrisReverseList(TreeNode head) {
	TreeNode cur = head;
	TreeNode pre = null;
	while (cur != null) {
		TreeNode next = cur.right;
		cur.right = pre;
		pre = cur;
		cur = next;
	}
	return pre;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49