先序遍历

例题： https://leetcode-cn.com/problems/binary-tree-preorder-traversal/

1
2
3
4
5
6
7
8
public void traversal(TreeNode root) {
	if(root == null){
		return;
	}
	System.out.println(root.val);	// 根
	traversal(root.left);	//左
	traversal(root.right);	//右
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public void traversal(TreeNode root){
	// 先判断树是否为空
	if(root == null){
		return;
	}
	Deque<TreeNode> stack = new LinkedList<>();
	while(root != null || !stack.isEmpty()){
		while(root != null){
			System.out.println(root.val);	// 根
			stack.push(root);
			root = root.left;	// 左		
		}
		root = stack.pop();	//到这代表左树为null或遍历完毕
		root = root.right;	//右
	}
}

利用栈通过类似于层序遍历的方法实现先序遍历，也算是一种迭代

思路： 若树不为空，先将根结点入栈。之后在循环内删除并得到栈顶结点，输出其值后依次将右、左儿子入栈。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public void traversal(TreeNode root){
	// 先判断树是否为空
	if(root == null){
		return;
	}
	Deque<TreeNode> stack = new LinkedList<>();
	stack.push(root);	// 先把根结点入栈
	while(!stack.isEmpty()){
		root = stack.pop();
		System.out.println(root.val);
		if(root.right != null){
			stack.push(root.right);
		}
		if(root.left != null){
			stack.push(root.left);
		}
	}
}

中序遍历

例题： https://leetcode-cn.com/problems/binary-tree-inorder-traversal/

1
2
3
4
5
6
7
8
public void traversal(TreeNode root) {
	if(root == null){
		return;
	}
	traversal(root.left);	// 左
	System.out.println(root.val);	// 根
	traversal(root.right);	// 右
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public void traversal(TreeNode root){
	if(root == null){
		return;
	}
	Deque<TreeNode> stack = new LinkedList<>();
	while(root != null || !stack.isEmpty()){
		while(root != null){
			stack.push(root);
			root = root.left;	// 左			
		}
		root = stack.pop(); // 到这代表左树为null或遍历完毕
		System.out.println(root.val);	// 根
		root = root.right;	// 右
	}
}

后序遍历

例题： https://leetcode-cn.com/problems/binary-tree-postorder-traversal/

1
2
3
4
5
6
7
8
9
public void traversal(TreeNode root) {
	if(root == null){
		return;
	}
	traversal(root.left);	// 左
	traversal(root.right);	// 右
	System.out.println(root.val);	// 根

}

相比先序和中序更复杂一点，因为是先遍历左、右子树再输出根结点，所以可能需要二次入栈。

思路： 用一个指针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
public void traversal(TreeNode root){
	// 先判断是不是空树
	if(root != null){
		return;
	}
	Deque<TreeNode> stack = new LinkedList<>();
	TreeNode pre = null;	// 创建指针来判断是 输出根结点 还是 遍历该根结点的右孩子
	while(root != null || !stack.isEmpty()){
		while(root != null){
			stack.push(root);
			root = root.left;	// 左
		}
		root = stack.pop();	//到这时代表该结点左子树为null或遍历完毕
		// 若该结点存在右孩子且右孩子没有被遍历过，则先遍历右孩子
		if(root.right != null && root.right != pre){
			stack.push(root);	// 还需遍历该结点的右孩子才能输出该结点，将该结点二次入栈
			root = root.right;	// 右
		}else{
			System.out.println(root.val);	// 根
			pre = root;	// 代表该结点（上一个结点的右孩子）已经遍历过了
			root = null;	// 将root 设为 null，让下次循环得到栈顶结点（父结点）
		}
	}
}

利用了辅助栈，通过反转逆后序遍历，实现后序遍历

思路： 将先序遍历的左孩子和右孩子操作调换，得到逆后序 根、右、左。再将结果依次入到辅助栈中，利用栈先入后出的顺序，反转逆后序得到 左、右、根 后序输出

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public void traversal(TreeNode root){
	// 先判断树是否为空
	if(root == null){
		return;
	}
	Deque<TreeNode> stack = new LinkedList<>();
	Deque<Integer> helpStack = new LinkedList<>(); // 辅助栈 
	// 实现逆后序，将输出元素依次进入辅助栈
	while(root != null || !stack.isEmpty()){
		while(root != null){
			helpStack.push(root.val);	// 根
			stack.push(root);
			root = root.right;	// 右
		}
		root = stack.pop();	//到这代表右树为null或遍历完毕
		root = root.left;	//左
	}
	// 输出辅助栈内元素，实现反转逆后序
	while(!helpStack.isEmpty()){
		System.out.println(helpStack.pop());	// 根右左 -> 左右根
	}
}

结合先序迭代2方法和后序迭代2方法同样可以实现可以实现
先用先序迭代2方法实现逆后序，再用后序迭代2方法实现反转逆后序得到后序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public void traversal(TreeNode root){
	// 先判断树是否为空
	if(root == null){
		return;
	}
	Deque<TreeNode> stack = new LinkedList<>();
    Deque<Integer> helpStack = new LinkedList<>(); // 辅助栈 
	stack.push(root);	// 先把根结点入栈
    // 辅助站内元素顺序为 根、右、左
	while(!stack.isEmpty()){
		root = stack.pop();
		helpStack.push(root.val);
		if(root.left != null){
			stack.push(root.right);
		}
		if(root.right != null){
			stack.push(root.left);
		}
	}
    // 输出辅助栈内元素，实现反转逆后序
	while(!helpStack.isEmpty()){
		System.out.println(helpStack.pop());	// 根右左 -> 左右根
	}
}

层序遍历

例题： https://leetcode-cn.com/problems/binary-tree-level-order-traversal/

  1. 层序遍历的实现需要利用到队列。
  2. 层序遍历是从上至下，从左至右遍历输出的。
  3. 具体步骤为：根结点入队 -> while{出队 -> 输出 -> 左右孩子入队}

例如：[A],[BC],[EFGH],[IZ]

通过获取当前队列的大小，再根据大小设置循环，循环内输出同一层的结点值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public void traversal(TreeNode root){
	// 先判断是不是空树
	if(root == null){
		return;
	}
	Deque<TreeNode> queue = new ArrayDeque<>();
	queue.offer(root);	// 根结点入队
	while(!queue.isEmpty()){
		int size = queue.size();	// 获取当前队列的大小（当前层数有多少结点）
		List<Integer> list = new ArrayList<>();	// 储存同一层内的结点
		// 通过循环将当前层内的结点依次出队并将值添加到集合中再统一输出
		for(int i = 0; i < size; i++){
			root = queue.poll();
			list.add(root.val);
			if(root.left != null){
				queue.offer(root.left);
			}
			if(root.right != null){
				queue.offer(root.right);
			}
		}
		System.out.println(list);
	}
}

例如：A,B,C,D,E,F,G,H,I,Z

存在限制，在需要利用到层数分类的题中不适用

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public void traversal(TreeNode root){
	// 先判断是不是空树
	if(root == null){
		return;
	}
	Deque<TreeNode> queue = new ArrayDeque<>();
	queue.offer(root);	// 先将根结点入栈
	while(!queue.isEmpty()){
		root = queue.poll();
		System.out.println(root.val);
		if(root.left != null){
			queue.offer(root.left);
		}
		if(root.right != null){
			queue.offer(root.right);
		}
	}
}