二叉树层次遍历(力扣102/1722)

电玩女神 2023-03-01 11:45 5阅读 0赞

[102. 二叉树的层序遍历][102.]

难度中等569收藏分享切换为英文关注反馈

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

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

3
       / \
      9  20
        /  \
       15   7

返回其层次遍历结果：

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

--------------------

## 层次遍历模板（队列） ##

public void bfs(TreeNode root){
        Queue<TreeNode> queue = new LinkedList<>();
        if(root != null)
            queue.offer(root);
        while(!queue.isEmpty()){
            root = queue.poll();
            if(root.left != null)
                queue.offer(root.left);
            if(root.right != null)
                queue.offer(root.right);
        }
    }

/**
     * Definition for a binary tree node.
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode(int x) { val = x; }
     * }
     */
    class Solution {
        public List<List<Integer>> levelOrder(TreeNode root) {
            if(root==null)return new ArrayList();
            List<List<Integer>> res=new ArrayList<>();
            bfs(res,root);
            return res;
        }
        public void bfs(List<List<Integer>> res,TreeNode root){
            if(root==null)return;
            Deque<TreeNode> queue=new LinkedList<TreeNode>();
            queue.offer(root);
            while(!queue.isEmpty()){
                int count=queue.size();//记录每层的节点数
                List<Integer> tmp=new ArrayList<Integer>();
                while(count-->0){
                    TreeNode node=queue.poll();
                    tmp.add(node.val);
                    if(node.left!=null){
                        queue.offer(node.left);
                    }
                    if(node.right!=null){
                        queue.offer(node.right);
                    }
                }
                res.add(tmp);
            }
        }
    }

[102.]: https://leetcode-cn.com/problems/binary-tree-level-order-traversal/