题目

94. 二叉树的中序遍历 - 力扣（Leetcode）

145. 二叉树的后序遍历 - 力扣（Leetcode）

144. 二叉树的前序遍历 - 力扣（Leetcode）

102. 二叉树的层序遍历 - 力扣（Leetcode）

二叉树遍历方式

  • 深度优先遍历
    • 前序（迭代，递归）
    • 中序（迭代，递归）
    • 后序（迭代，递归）
  • 广度优先遍历
    • 层次遍历（迭代）

怎么看前中后：父节点在哪就是什么序。

深度遍历：一般都是用递归。用栈也可以。

广度遍历：用队列比较多。

二叉树遍历

深度优先

用栈实现first，递归实现大家都会。

下次直接练习统一迭代实现吧。

递归实现

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
50
51
class Solution {
    //前序
     public List<Integer> preorderTraversal(TreeNode root) {
    	List<Integer> res = new ArrayList<Integer>();
    	preorder(root, res);
    	return res;
    }
    void preorder(TreeNode root, List<Integer> res){
    	//迭代结束点
    	if (root == null) {
    		return;
    	}
    	//前序遍历
    	res.add(root.val);
    	preorder(root.left, res);
    	preorder(root.right, res);
    }
    //中序
    public List<Integer> inorderTraversal(TreeNode root) {
    	List<Integer> res = new ArrayList<Integer>();
    	inorder(root, res);
    	return res;
    }
    void inorder(TreeNode root, List<Integer> res){
    	//迭代结束点
    	if (root == null) {
    		return;
    	}
    	//中序遍历
    	inorder(root.left, res);
    	res.add(root.val);
    	inorder(root.right, res);
    }
	//后序
    public List<Integer> postorderTraversal(TreeNode root) {
    	List<Integer> res = new ArrayList<Integer>();
    	postorder(root, res);
    	return res;
    }
    void postorder(TreeNode root, List<Integer> res){
    	//迭代结束点
    	if (root == null) {
    		return;
    	}
    	//后序遍历
    	postorder(root.left, res);
    	postorder(root.right, res);
    	res.add(root.val);
    }
   
}

栈实现

栈实现(这个有点难度)

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
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
class Solution2 {
    public List<Integer> inorderTraversal(TreeNode root) {
    	List<Integer> res = new ArrayList<>();
    	if (root == null) {
    		return res;
    	}
    	//栈
    	Stack<TreeNode> stack  = new Stack<>();
    	
    	TreeNode temp = root;

    	while(temp != null || !stack.isEmpty()){
    		if (temp != null) {
    			stack.push(temp);
    			temp = temp.left;
    		}else{
    			temp = stack.pop();
    			res.add(temp.val);
    			temp = temp.right;
    		}
    	}
    	return res;
    }
    

    public List<Integer> postorderTraversal(TreeNode root) {
    	List<Integer> res = new ArrayList<>();
    	if (root == null) {
    		return res;
    	}
    	//栈
    	Stack<TreeNode> stack  = new Stack<>();
    	stack.push(root);
    	TreeNode temp;

    	while(!stack.isEmpty()){
    		//栈没有空就继续干
    		temp = stack.pop();
    		res.add(temp.val);
    		if (temp.left != null) {
    			stack.push(temp.left);
    		}
    		if (temp.right != null) {
    			stack.push(temp.right);
    		}
    	}
    	Collections.reverse(res);
    	return res;
    }
   
    public List<Integer> preorderTraversal(TreeNode root) {
    	List<Integer> res = new ArrayList<>();
    	if (root == null) {
    		return res;
    	}
    	//栈
    	Stack<TreeNode> stack  = new Stack<>();
    	stack.push(root);
    	TreeNode temp;

    	while(!stack.isEmpty()){
    		//栈没有空就继续干
    		temp = stack.pop();
    		res.add(temp.val);
    		if (temp.right != null) {
    			stack.push(temp.right);
    		}
    		if (temp.left != null) {
    			stack.push(temp.left);
    		}
    	}
    	return res;
    }
}

统一迭代实现

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
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75

class Solution3 {
    //中序遍历
    public List<Integer> inorderTraversal(TreeNode root) {
    	List<Integer> res = new LinkedList<>();
    	if(root == null){
    		return res;
    	}
    	Stack<TreeNode> stack = new Stack<>();
    	stack.push(root);
    	TreeNode temp;
    	while(!stack.isEmpty()){
    		temp = stack.pop();
    		if (temp != null) {
    			if (temp.right != null) stack.push(temp.right);
    			stack.push(temp);
    			stack.push(null);
    			if (temp.left != null) stack.push(temp.left);
    		}else{
    			temp = stack.pop();
    			res.add(temp.val);
    		}
    	}
    	return res;
    }
    

    public List<Integer> postorderTraversal(TreeNode root) {
    	List<Integer> res = new LinkedList<>();
    	if(root == null){
    		return res;
    	}
    	Stack<TreeNode> stack = new Stack<>();
    	stack.push(root);
    	TreeNode temp;
    	while(!stack.isEmpty()){
    		temp = stack.pop();
    		if (temp != null) {
    			stack.push(temp);
    			stack.push(null);
    			if (temp.right != null) stack.push(temp.right);
    			if (temp.left != null) stack.push(temp.left);
    		}else{
    			temp = stack.pop();
    			res.add(temp.val);
    		}
    	}
    	return res;
    }
   
    public List<Integer> preorderTraversal(TreeNode root) {
    	List<Integer> res = new LinkedList<>();
    	if(root == null){
    		return res;
    	}
    	Stack<TreeNode> stack = new Stack<>();
    	stack.push(root);
    	TreeNode temp;
    	while(!stack.isEmpty()){
    		temp = stack.pop();
    		if (temp != null) {
    			if (temp.right != null) stack.push(temp.right);
    			if (temp.left != null) stack.push(temp.left);
    			stack.push(temp);
    			stack.push(null);
    		}else{
    			temp = stack.pop();
    			res.add(temp.val);
    		}
    	}
    	return res;
    }
    
}

就是父节点后面要个null，记住规则然后知道了就很好模仿。

广度优先

这个多写几遍就会了。

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

//层序遍历
class Solution {

    public List<List<Integer>> levelOrder(TreeNode root) {
    	//返回的ret
    	List<List<Integer>> ret = new ArrayList<List<Integer>>();
    	//安全性校验
    	if (root == null) {
    		return ret;
    	}
    	//队列
    	Queue<TreeNode> que = new LinkedList<TreeNode>();
    	//让root直接入队列
    	que.offer(root);
    	
    	while(!que.isEmpty()){
    		//构建这层的List
    		List<Integer> itemList = new ArrayList<Integer>();
    		int len = que.size();
    		//临时工TreeNode节点
    		TreeNode temp;

    		while(len-- > 0){
    			//拿出队列的第一个
    			temp = que.poll();
    			//给到这层的那个itemList
    			itemList.add(temp.val);
    			//补充这个的左右两个
    			if (temp.left != null) que.offer(temp.left);
    			if (temp.right != null) que.offer(temp.right);
    		}
    		ret.add(itemList);
    	}
    	return ret;
    }
}