剑指 Offer 32 - II. 从上到下打印二叉树 II

我会带着你远行 2022-12-09 14:58 107阅读 0赞

**题目：**  
从上到下按层打印二叉树，同一层的节点按从左到右的顺序打印，每一层打印到一行。

**例如:**

给定二叉树: [3,9,20,null,null,15,7],
    
        3
       / \
      9  20
        /  \
       15   7
    返回其层次遍历结果：
    
    [
      [3],
      [9,20],
      [15,7]
    ]

**提示：**

*  节点总数 <= 1000

**题解：**

/** * 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) { 
            
            List<List<Integer>> res = new ArrayList();
            
            helper(res,root,0);
            return res;
        }
        public void helper(List<List<Integer>> res,TreeNode node,int k){ 
            if(node == null) { 
                return ;
            }
            if(k >= res.size()) { 
                res.add(new ArrayList());
            }
            
            res.get(k).add(node.val);
            
            helper(res,node.left,k+1);
            helper(res,node.right,k+1);
            
            
            
        }
    
    }

/** * 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<>();
        //队列
        Queue<TreeNode> queue = new LinkedList<>();
        List<List<Integer>> res = new ArrayList<>();
        //根节点入队
        queue.add(root);
        //如果队列不为空就继续循环
        while (!queue.isEmpty()) { 
            //BFS打印，levelNum表示的是每层的结点数
            int levelNum = queue.size();
            //subList存储的是每层的结点值
            List<Integer> subList = new ArrayList<>();
            for (int i = 0; i < levelNum; i++) { 
                //出队
                TreeNode node = queue.poll();
                subList.add(node.val);
                //左右子节点如果不为空就加入到队列中
                if (node.left != null)
                    queue.add(node.left);
                if (node.right != null)
                    queue.add(node.right);
            }
            //把每层的结点值存储在res中，
            res.add(subList);
        }
        return res;
    }
    
    }