层次遍历的递归实现 Java

Java 中的二叉树结构的表示

public class TreeNode {
	int val;
	TreeNode left;
	TreeNode right;

	TreeNode(int x) {
		val = x;
	}
}

一个简单的二叉树层序遍历题目

二叉树

    3
   / \
  9  20
    /  \
   15   7

请给出二叉树的 层序遍历序列：

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

二叉树的层序遍历（递归实现）

我们需要一个二维列表存储每一层的元素。

Java中这样定义一个二维列表：
List<List> levels = new ArrayList<>();

• 二维表的索引——该索引指向的嵌套列表位于第几层。
  例如二维表索引 levels[0]处，表示的是第一层。第一层中存储了根节点
• 每一层的都在第一次进入的时候创建

代码如下：

class Solution {
    // 递归层序遍历，递归的时候传递当前层数
    List<List<Integer>> levels = new ArrayList<List<Integer>>();
    public List<List<Integer>> levelOrder(TreeNode root) {
       if(root == null) return levels;
       levelBuilder(root, 0);
       return levels;
    }
    
    public void levelBuilder(TreeNode root, int level){
        // 如果当前层未被创建过，则创建
        if(level >= levels.size()){
            levels.add(new ArrayList<Integer>());
        }
        // 添加元素进当前层的list集合中
        levels.get(level).add(root.val);
        if(root.left != null) levelBuilder(root.left, level+1);
        if(root.right != null) levelBuilder(root.right, level+1);
    }
}

注意递归的传参

更简洁的代码：

class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> result = new ArrayList<List<Integer>>();
        helper(root, 0, result);
        return result;
    }

    public void helper(TreeNode root, int level, List<List<Integer>> lists) {
        if (root == null) {
            return;
        }
        if (lists.size() < level + 1) {
            lists.add(new ArrayList<Integer>());
        }
        lists.get(level).add(root.val);
        helper(root.left, level + 1, lists);
        helper(root.right, level + 1, lists);
    }
}

将 result二维列表当做参数传递进去，root判空操作在递归函数(helper)内部进行。
这样 levelOrder不需要处理很多的逻辑，很是简洁。

二叉树的层序遍历（非递归实现）

通过队列实现，先进第一个根节点入队列。

此时队列中只有一个元素，size=1。 所以只会把根节点的左右孩子入队列（非空的时候）

然后假设左右孩子都不是null，那么此时 队列的size=2，所以会将根节点的左右孩子的孩子分别入队列，假设他们都不是null的话，此时队列中的size=4。

依次下去，每次通过遍历size可以控制从集合中出来的正好是上一层中的所有非null元素

class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        List<List<Integer>> lists = new ArrayList<>();
        if(root == null) return lists;
        queue.offer(root);
        while(!queue.isEmpty()){
        	// 这里的 size很关键，存储每一层节点数
            int size = queue.size();
            List<Integer> list = new ArrayList<Integer>();
            // 在这里，根据 size，把每一层节点的所有左右孩子都添加都队列里头
            while(size-- > 0){
                root = queue.poll();
                list.add(root.val);
               if(root.left != null) queue.offer(root.left);
                if(root.right != null) queue.offer(root.right); 
            } 
            lists.add(list);
        }
        return lists;
    }
}