【LeetCode 102】算法：二叉树的层序遍历

junjunyi

27天前发布

题目：给你二叉树的根节点 root ，返回其节点值的层序遍历。（即逐层地，从左到右访问所有节点）。

算法思路：

用 Queue 存放当前层的节点。
每轮循环处理一整层，把节点值收集到 List 。
依次把左右子节点入队。

复杂度：

时间复杂度：O(n) —— 每个节点恰好访问一次
空间复杂度：O(n) —— 队列最大宽度（最底层节点数）

补充：如果只想拿到层序遍历的一维列表，去掉 curLevel 的收集，直接 res.add(node.val) 即可。

Java 代码实现：

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */

class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {

        List<List<Integer>> res = new ArrayList<>();
        if(root==null) return res;
        Queue<TreeNode> q = new LinkedList<>();

        // 1、根节点入队
        q.offer(root);

        // 把每一层的节点数组（子数组），加入到最终集合
        while(!q.isEmpty()){
            int num = q.size(); // 每层的宽度
            List<Integer> level = new ArrayList<>(); // 存储当前层的全部结点

            // 2、遍历当前层：每次循环，从队头取出一个节点，直到取完此层
            for(int i=0; i<num; i++){
                // 3、取出节点，把节点加入子数组
                TreeNode node = q.poll();
                level.add(node.val);
                // 4、取出节点后，要把它的子结点加入队列
                if(node.left != null)  q.offer(node.left);
                if(node.right != null) q.offer(node.right);
            }
            // 5、把子数组加入最终结果
            res.add(level); 
        }

        return res;
    }
}

来源链接：https://www.cnblogs.com/Junjunyi/p/19027007

评分

欢迎为Ta评分