二叉树的层序遍历

发布于 — 2020 年 03 月 03 日
#树

题目链接

力扣

给你二叉树的根节点 root, 返回其节点值的 层序遍历. (即逐层地, 从左到右访问所有节点).

输入：root = [3,9,20,null,null,15,7]
输出：[[3],[9,20],[15,7]]

广度优先遍历的一个变种, 需要每一层放到一个数组中.

每次对队列遍历时, 当前队列的长度就是这一层的数据, 所以先获取到当前层的元素数量

 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 List<List<Integer>> levelOrder(TreeNode root) {
		if (root == null) {
			return Collections.emptyList();
		}
		List<List<Integer>> res = new LinkedList<>();
		Queue<TreeNode> queue = new LinkedList<>();
		queue.add(root);
		while (!queue.isEmpty()) {
			int curLevelSize = queue.size();
			List<Integer> curList = new LinkedList<>();
			for (int i = 0; i < curLevelSize; i++) {
				TreeNode node = queue.poll();
				curList.add(node.val);
				if (node.left != null) {
					queue.add(node.left);
				}
				if (node.right != null) {
					queue.add(node.right);
				}
			}
			res.add(curList);
		}
		return res;
    }

变种

力扣

输入：root = [3,9,20,null,null,15,7]
输出：[[15,7],[9,20],[3]]

这次要求, 结果中, 先放最下层节点

我们利用Java中的List特性, 在每次插入一层的数据时, 将其插入到最开始的位置.

 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 List<List<Integer>> levelOrderBottom(TreeNode root) {
		if (root == null) {
			return Collections.emptyList();
		}
		List<List<Integer>> res = new LinkedList<>();
		Queue<TreeNode> queue = new LinkedList<>();
		queue.add(root);
		while (!queue.isEmpty()) {
			int curLevelSize = queue.size();
			List<Integer> curList = new LinkedList<>();
			for (int i = 0; i < curLevelSize; i++) {
				TreeNode node = queue.poll();
				curList.add(node.val);
				if (node.left != null) {
					queue.add(node.left);
				}
				if (node.right != null) {
					queue.add(node.right);
				}
			}
			res.add(0, curList);
		}
		return res;
	}