LeetCode百题【二叉树的层序遍历】

题目描述

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

示例 1：

1 2	`输入：root = [3,9,20,null,null,15,7] 输出：[[3],[9,20],[15,7]]`

示例 2：

1 2	`输入：root = [1] 输出：[[1]]`

示例 3：

1 2	`输入：root = [] 输出：[]`

提示：

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

解法

dfs
- 通过标识节点层级，将同一层级的节点加入即可

class Solution {
    List<List<Integer>> res=new ArrayList<>();

    public List<List<Integer>> levelOrder(TreeNode root) {
        if (root==null){
            return res;
        }
        helper(root, 0);
        return res;
    }
    /**
     * 维护的dfs
     * @param node 当前节点
     * @param level 所在层级
     */
    public void helper(TreeNode node,int level){
        if (level==res.size()){
            res.add(new ArrayList<Integer>());
        }
        res.get(level).add(node.val);
        if (node.left!=null){
            helper(node.left, level+1);
        }
        if (node.right!=null){
            helper(node.right, level+1);
        }
    }
}

时间复杂度：O(n)

bfs
- 通过队列辅助进行广度优先搜索

class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> res=new ArrayList<>();
        if (root==null){
            return res;
        }
        
        //队列辅助广度优先搜索
        Queue<TreeNode> queue=new LinkedList<>();
        queue.add(root);

        //每次处理一层的节点
        while (!queue.isEmpty()){
            List<Integer> temp=new ArrayList<>();
            int currentSize=queue.size();//获取实时队列长度
            for (int i = 0; i < currentSize; i++) {
                TreeNode pollNode = queue.poll();
                temp.add(pollNode.val);
                if (pollNode.left!=null){
                    queue.add(pollNode.left);
                }
                if (pollNode.right!=null){
                    queue.add(pollNode.right);
                }
            }
            res.add(temp);
        }
    return  res;
    }

}