当前位置:   article > 正文

力扣102 二叉树的层序遍历 Java版本

力扣102 二叉树的层序遍历 Java版本


题目描述

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

示例 1:
在这里插入图片描述

输入:root = [3,9,20,null,null,15,7]
输出:[[3],[9,20],[15,7]]
示例 2:

输入:root = [1]
输出:[[1]]
示例 3:

输入:root = []
输出:[]

提示:

树中节点数目在范围 [0, 2000] 内
-1000 <= Node.val <= 1000

思路

这个问题可以用队列解决。先把根节点入队,然后队列不空的话就出队,出队的同时遍历出队节点,如果当前节点有孩子节点就把孩子节点入队,这样遍历的顺序就是从上到下、从左到右,满足层序遍历。
在代码中详细注释了怎么一层一层地统计结果。

代码

class Solution {
    //层序遍历
    public List<List<Integer>> levelOrder(TreeNode root) {
        ArrayList<List<Integer>> result = new ArrayList<>();
        if (root == null) {
            return result;
        }

        //将根节点入队
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {

            //求一下当前队列中元素的个数,这个数也就是表示这一层有多少个节点
            //因为下一层的还没有开始入队,上一层的都已经出队了,队列中的元素就都是这一层的了
            int length = queue.size();
            //因为最后要求返回的结果是分层的,所以按照层进行循环,添加到result中
            List<Integer> list = new ArrayList<>();
            while (length > 0) {
                //取出队头节点
                TreeNode node = queue.poll();
                list.add(node.val);
                //如果这个节点的左右孩子不为空,就将左右孩子入队
                if (node.left != null) {
                    queue.offer(node.left);
                }
                if (node.right != null) {
                    queue.offer(node.right);
                }
                length--;
            }
            //将这一层的结果加入到result中
            result.add(list);

        }

        return result;
    }
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/2023面试高手/article/detail/146048
推荐阅读
相关标签
  

闽ICP备14008679号