刷题记录----二叉树的层序遍历

目录

题目描述：给定一个二叉树，返回其层序遍历的结果

结合辅助队列，两层循环，从上到下，从左到右遍历，结果即为层序遍历

递归：

---

题目描述：给定一个二叉树，返回其层序遍历的结果

结合辅助队列，两层循环，从上到下，从左到右遍历，结果即为层序遍历

void levelTraverse(TreeNode root) {
    if (root == null) return;
    Queue<TreeNode> q = new LinkedList<>();
    q.offer(root);

    // 从上到下遍历二叉树的每一层
    while (!q.isEmpty()) {
        int sz = q.size();
        // 从左到右遍历每一层的每个节点
        for (int i = 0; i < sz; i++) {
            TreeNode cur = q.poll();
            // 将下一层节点放入队列
            if (cur.left != null) {
                q.offer(cur.left);
            }
            if (cur.right != null) {
                q.offer(cur.right);
            }
        }
    }
}

递归：

class Solution {
    List<List<Integer>> list = new ArrayList<>();
    public List<List<Integer>> levelOrder(TreeNode root) {
        dns(root,0);
        return list;
    }
    public void dns(TreeNode node,int lever){
        if(node == null) return;
        if(list.size()==lever) list.add(new ArrayList<Integer>());

        list.get(lever).add(node.val);

        dns(node.left,lever+1);
        dns(node.right,lever+1);
    }
}