leetcode_【102】二叉树的层次遍历

1.题目描述

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

例如:
给定二叉树: [3,9,20,null,null,15,7],

>      3
>     / \
>    9  20
>       / \
>      15  7
>

返回其层次遍历结果：

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

2.解题思路

同【剑指offer - 60】

BFS广度优先搜索的扩展题

迭代思想：

我们将树上顶点按照层次依次放入队列结构中，队列中元素满足 FIFO（先进先出）的原则。在 Java 中可以使用 Queue 接口中的 LinkedList实现。

第 0 层只包含根节点 root ，算法实现如下：

(1)初始化队列只包含一个节点 root 和层次编号 0 ： level = 0。
(2)当队列非空的时候：
    1) 在输出结果 levels 中插入一个空列表，开始当前层的算法。
    2)计算当前层有多少个元素：等于队列的长度。
    3)将这些元素从队列中弹出，并加入 levels 当前层的空列表中。
    4)将他们的孩子节点作为下一层压入队列中。
    5)进入下一层 level++。

递归思想：
最简单的解法就是递归，首先确认树非空，然后调用递归函数 helper(node, level)，参数是当前节点和节点的层次。程序过程如下：
(1)输出列表称为 ans，当前最高层数就是列表的长度 len(ans)。比较访问节点所在的层次 level 和当前最高层次 len(ans) 的大小，如果前者更大就向 ans 添加一个空列表。
(2)将当前节点插入到对应层的列表 ans[level] 中。
(3)递归非空的孩子节点：helper(node.left , level + 1)。helper(node.right, level + 1)。

3.代码

方法1：迭代

执行用时 :

    3 ms, 在所有 Java 提交中击败了55.91%的用户

内存消耗 :
    36.5 MB, 在所有 Java 提交中击败了44.59%的用户
  public List<List<Integer>> levelOrder(TreeNode root) {
        //用于记录所有结果
        List<List<Integer>> lists = new ArrayList<>();
        if(root == null)
            return lists;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        while(!queue.isEmpty()){
           //用于保存当前层的节点数
           ArrayList<Integer> tmp = new ArrayList<>();
           //当前层包含的节点个数
           int count = queue.size();
           for(int i = 0; i<count;i++){
              //删除并返回queue中的头元素，删掉根（上一层结点元素）
               TreeNode node = queue.poll();
               //加入左子树
               if(node.left!=null)
                   queue.add(node.left);
               //加入右子树
               if(node.right!=null)
                   queue.add(node.right);
               //加入当前层的节点
               tmp.add(node.val);
           }
           lists.add(tmp);
        }
    return lists;
    }

方法2：递归

执行用时 :
    2 ms, 在所有 Java 提交中击败了92.32%的用户
内存消耗 :
    37.1 MB, 在所有 Java 提交中击败了42.97%的用户
class Solution {
    List<List<Integer>> ans = new ArrayList<List<Integer>>();

    public List<List<Integer>> levelOrder(TreeNode root) {
        if(root == null)
            return ans;
        helper(root,0);
        return ans;
    }

    private void helper(TreeNode root, int level) {
        if(ans.size() == level)
            ans.add(new ArrayList<>());
        ans.get(level).add(root.val);

        if(root.left != null)
            helper(root.left,level+1);
        if(root.right != null)
            helper(root.right,level+1);
    }
}

4.提交结果