NC15 求二叉树的层序遍历

NC15 求二叉树的层序遍历 考过的企业 - 小米

题目描述

给定一个二叉树，返回该二叉树层序遍历的结果，（从左到右，一层一层地遍历）
例如：
给定的二叉树是{3,9,20,#,#,15,7},

img

该二叉树层序遍历的结果是
[
[3],
[9,20],
[15,7]
]

考察关键点

1. 二叉树的层序遍历，用广度优先搜索（BFS），广度优先搜索使用队列来实现
2. 该题目的返回结果要求返回结果中包含层信息，思考如何在BFS中融合如层序信息

解题思路

1. 如果不考虑层序信息，BFS可以很简单的使用一个队列实现，如下代码是按照层序打印遍历结果

   public void levelOrder(TreeNode root) {
    LinkedList<TreeNode> queue = new LinkedList<>();
       queue.add(root);
       while (!queue.isEmpty()) {
        TreeNode top = queue.pop();
           System.out.println(top.val);
           if (top.left != null) {
               queue.add(top.left);
           }
           if (top.right != null) {
               queue.add(top.right);
           }
       }
   }
   

2. 上面代码简单BFS已经让我们获取到了层序的遍历结果，但是此处还不包含打印的节点在二叉树的哪一层的信息，那我们尝试修改上述代码来增加层数信息。这里我们尝试在这个while循环上做做文章，若每次while循环只处理同一层的节点，并在循环中把这一层所有节点的值放入一个列表中存入结果集，那么就可以求出题目要求的结果，那么现在这个问题就变成，如何保证一次while循环只处理二叉树一层的节点呢？这里我们再回到帮助我们进行BFS的队列，如果我们能保证每次开始一次while循环时，队列里只有同一层的数据，并且处理完这一层所有的数据后，再进入下一次循环，那么这个问题就解决了，OK，直接看代码。

       public static ArrayList<ArrayList<Integer>> levelOrder(TreeNode root) {
           ArrayList<ArrayList<Integer>> ret = new ArrayList<>();
           if (root == null) {
               return ret;
           }
           // 用于BFS的队列
           LinkedList<TreeNode> queue = new LinkedList<>();
           queue.add(root);
           while (!queue.isEmpty()) {
               int len = queue.size();
               // 初始化同一层的数组
               ret.add(new ArrayList<>());
               // 进入while循环时，队列中都是同一层的节点，并且在本次while循环中将这一层的所有节点处理完，所以这里取一开始进入循环时的队列长度，并取出同一层所有的节点放入结果集
               for (int i = 0; i < len; i++) {
                   TreeNode top = queue.pop();
                   // 放入这一层对应的数组中
                   ret.get(ret.size() - 1).add(first.val);
                   System.out.println(top.val);
                   // 将下一层的节点放入队列，准备进行下一次while循环
                   if (top.left != null) {
                       queue.add(top.left);
                   }
                   if (top.right != null) {
                       queue.add(top.right);
                   }
               }
   
           }
           return ret;
       }
   

完整代码

package NC15;

import java.util.*;


class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;


    public TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}


public class NC15 {
    /**
     * @param root TreeNode类
     * @return int整型ArrayList<ArrayList<>>
     */
    public static ArrayList<ArrayList<Integer>> levelOrder(TreeNode root) {
        ArrayList<ArrayList<Integer>> ret = new ArrayList<>();
        if (root == null) {
            return ret;
        }
        LinkedList<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        while (!queue.isEmpty()) {
            int len = queue.size();
            ret.add(new ArrayList<>());
            for (int i = 0; i < len; i++) {
                TreeNode top = queue.pop();
                ret.get(ret.size() - 1).add(first.val);
                System.out.println(top.val);
                if (top.left != null) {
                    queue.add(top.left);
                }
                if (top.right != null) {
                    queue.add(top.right);
                }
            }

        }
        return ret;
    }

    public static void main(String[] args) {
        TreeNode root = new TreeNode(3, new TreeNode(9, new TreeNode(15, null, null), new TreeNode(7, null, null)), new TreeNode(20, null, null));
        System.out.println(levelOrder(root));
    }

}