LeetCode： 102. Binary Tree Level Order Traversal 按层打印二叉树

红太狼 2021-06-24 16:11 339阅读 0赞

**试题**  
Given a binary tree, return the level order traversal of its nodes’ values. (ie, from left to right, level by level).

For example:  
Given binary tree \[3,9,20,null,null,15,7\],

3
       / \
      9  20
        /  \
       15   7

return its level order traversal as:

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

**代码**

使用队列打印即可。

/**
     * 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>> out = new ArrayList<List<Integer>>();
            if(root==null) return out;
            
            ArrayDeque<TreeNode> que = new ArrayDeque<TreeNode>();
            que.offerLast(root);
            int len = que.size();
            
            while(!que.isEmpty()){
                ArrayList<Integer> tmp = new ArrayList<>();
                for(int i=0; i<len; i++){
                    TreeNode cur = que.pollFirst();
                    // if(cur!=null){
                    tmp.add(cur.val);
                    if(cur.left!=null)
                        que.offerLast(cur.left);
                    if(cur.right!=null)
                        que.offerLast(cur.right);
                    // }
                }
                len = que.size();
                // if(tmp.size()!=0)
                    out.add(tmp);
            }
            return out;
        }
    }