BM26. [求二叉树的层序遍历]

https://www.nowcoder.com/exam/oj?tab=%E7%AE%97%E6%B3%95%E7%AF%87&topicId=295

BM26. 求二叉树的层序遍历

https://www.nowcoder.com/practice/04a5560e43e24e9db4595865dc9c63a3?tpId=295&sfm=github&channel=nowcoder

那层序遍历又是怎么一回事呢？还是以刚才的二叉树为例，我们只要将每层的节点放入一个容器队列，那么就可以直接打印出来对应的就应该是层序遍历二叉树。

模板代码如下

public ArrayList<ArrayList<Integer>> levelOrder0 (TreeNode root) {
        ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
        if(root == null){
            return result;
        }
        LinkedList<TreeNode> queue = new LinkedList<TreeNode>();
        queue.offer(root);
        //while的一次循环遍历就必须吃掉里面所有的内容
        while(!queue.isEmpty()){
            int count = queue.size();
            ArrayList<Integer> rowList = new ArrayList<Integer>();
            while(count > 0){
                TreeNode curr = queue.poll();
                rowList.add(curr.val);
                if (curr.left != null){
                    queue.offer(curr.left);
                }
                if (curr.right != null){
                    queue.offer(curr.right);
                }
                --count;
            }
            result.add(rowList);
        }
        return result;
    }

既然层序遍历二叉树你已经掌握了，那么之字形打印二叉树不就是你的每层存储的容器打印的方向变化一下吗？仅仅需要增加如下代码。

//这个flag的设置就非常有创意      
boolean flag = false;
        .............
       if (flag){
         //翻转你的容器
                Collections.reverse(rowList);
            }
         //之字形转角
            flag = !flag;
       result.add(rowList);

完整代码

public class Solution {
    public ArrayList<ArrayList<Integer> > Print(TreeNode pRoot) {
          ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
        if(pRoot == null){
            return result;
        }
        LinkedList<TreeNode> queue = new LinkedList<TreeNode>();
        queue.offer(pRoot);
        //while的一次循环遍历就必须吃掉里面所有的内容
        boolean flag = false;
        while(!queue.isEmpty()){
            int count = queue.size();
            ArrayList<Integer> rowList = new ArrayList<Integer>();
            while(count > 0){
                TreeNode curr = queue.poll();
                rowList.add(curr.val);
                if (curr.left != null){
                    queue.offer(curr.left);
                }
                if (curr.right != null){
                    queue.offer(curr.right);
                }
                --count;
            }
            if (flag){
                Collections.reverse(rowList);
            }
            flag = !flag;
            result.add(rowList);
        }
        return result;
    }

}

复杂度分析

• 时间复杂度：，每个结点访问一次，，按每层元素也相当于
• 空间复杂度：，队列的空间