[数据结构与算法]leetcode102.二叉树的层序遍历

一.题目描述

给你一个二叉树，请你返回其按 层序遍历 得到的节点值。 （即逐层地，从左到右访问所有节点）。

示例：
二叉树：[3,9,20,null,null,15,7],

3

/
9 20
/
15 7
返回其层序遍历结果：

[
[3],
[9,20],
[15,7]
]

二.题目解析

public List<List<Integer>> levelOrder1(TreeNode root) {
         /*迭代-广度优先搜索
         利用队列的先进先出特性按序保存每层节点
         时间复杂度O(n),空间复杂度O(n)
         * */
         if (root == null)
             return new ArrayList<>();
         List<List<Integer>> res = new ArrayList<>();
         Queue<TreeNode> queue = new LinkedList<TreeNode>();
         //queue 初始时为 [root] ，代表第 1 层
         queue.add(root);
         while (!queue.isEmpty()) {
             //关键：count保存要处理的这一层的节点个数
             int count = queue.size();
             //list保存此层的所有节点值
             List<Integer> list = new ArrayList<Integer>();
             //这个while循环保证已处理的旧层的节点全部出去，待处理的新层节点全部进入
             while (count > 0) {
                 //当前层的节点逐个出列
                 TreeNode node = queue.poll();
                 //保存此元素的值
                 list.add(node.val);
                 //存在左孩子则左孩子进队列（下层节点）
                 if (node.left != null)
                     queue.add(node.left);
                 //存在右孩子则右孩子进队列（下层节点）
                 if (node.right != null)
                     queue.add(node.right);
                 count--;
             }
             res.add(list);
         }
         return res;
     }

2.

public List<List<Integer>> levelOrder(TreeNode root) {
         /*递归··深度优先搜索
         时间复杂度O(n),空间复杂度O(h)（二叉树高度）
         * */
         if (root == null) {
             return new ArrayList<List<Integer>>();
         }
         //用来存放最终结果
         List<List<Integer>> res = new ArrayList<List<Integer>>();
         dfs(1, root, res);
         return res;
     }

     void dfs(int index, TreeNode root, List<List<Integer>> res) {
         /*递归函数定义，层序遍历以root为根的二叉树的节点（root处于第index层）
         结果保存到res
         * */
         //假设res是[ [1],[2,3] ]， index是3，就再插入一个空list放到res中
         if (res.size() < index) {
             res.add(new ArrayList<Integer>());
         }
         //1.先把root节点值添加到res[index-1]数组里
         //将当前节点的值加入到res中，index代表当前层，假设index是3，节点值是99
         //res是[ [1],[2,3] [4] ]，加入后res就变为 [ [1],[2,3] [4,99] ]
         res.get(index - 1).add(root.val);
         //2.再递归的处理左子树，右子树，同时将层数index+1
         if (root.left != null) {
             dfs(index + 1, root.left, res);
         }
         if (root.right != null) {
             dfs(index + 1, root.right, res);
         }
     }

参考文章：
https://leetcode-cn.com/problems/binary-tree-level-order-traversal/solution/die-dai-di-gui-duo-tu-yan-shi-102er-cha-shu-de-cen/