1. 二叉树的定义
代码如下（java 语言实现）：
// Definition for a binary tree node.
public class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode() {}
TreeNode(int val) { this.val = val; }
TreeNode(int val, TreeNode left, TreeNode right) {
this.val = val;
this.left = left;
this.right = right;
}
}
2. 层序遍历实现
要进行层序遍历，需要借助一个队列。先将二叉树根节点入队，然后出队，访问出队结点。若它有左子树，则将左子树根节点入队；若它有右子树，则将右子树根节点入队。然后出队，访问出队结点。如此反复，直到队列为空。
代码如下（Java 语言实现）：
public List<List<Integer>> levelOrder(TreeNode root) {
if (root == null) return new ArrayList<>();
// 队列存放同一层的结点
Queue<TreeNode> dq = new LinkedList<>();
// 以每一层的结点值为一个 List,将所有层放入一个大的 List
List<List<Integer>> resList = new ArrayList<>();
dq.offer(root);
while (!dq.isEmpty()) {
int size = dq.size();
// 将同层结点值放入 List 中
List<Integer> res = new ArrayList<>();
while (size > 0) {
TreeNode node = dq.poll();
if (node.left != null) dq.offer(node.left);
if (node.right != null) dq.offer(node.right);
res.add(node.val);
size--;
}
resList.add(res);
}
return resList;
}
3. 复杂度分析
记树上所有节点的个数为 n.
时间复杂度：每个点进队出队各一次，故渐进时间复杂度为 O(n).
空间复杂度：队列中元素的个数不超过 n 个，故渐进空间复杂度为 O(n).
4. 总结
二叉树的层序遍历算法的代码实现，可以作为一个模板，将来用于解决于层序遍历相关的任何问题，一定要熟记于心！
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
文章由极客之音整理，本文链接：https://www.bmabk.com/index.php/post/5188.html
