二叉树的层次遍历

方法 1：递归

算法

最简单的解法就是递归，首先确认树非空，然后调用递归函数 helper(node, level)，参数是当前节点和节点的层次。程序过程如下：

输出列表称为 levels，当前最高层数就是列表的长度 len(levels)。比较访问节点所在的层次 level 和当前最高层次 len(levels) 的大小，如果前者更大就向 levels 添加一个空列表。
将当前节点插入到对应层的列表 levels[level] 中。
递归非空的孩子节点：helper(node.left / node.right, level + 1)。

代码Solution

package binary_tree_level_order_traversal;

import java.util.ArrayList;
import java.util.List;

/**
 * Definition for a binary tree node. public class TreeNode { int val; TreeNode
 * left; TreeNode right; TreeNode(int x) { val = x; } }
 */
class Solution {

    List<List<Integer>> levels = new ArrayList<List<Integer>>();

    public void helper(TreeNode node, int level) {
        // start the current level
        if (levels.size() == level)
            levels.add(new ArrayList<Integer>());

        // fulfil the current level
        levels.get(level).add(node.val);

        // process child nodes for the next level
        if (node.left != null)
            helper(node.left, level + 1);
        if (node.right != null)
            helper(node.right, level + 1);
    }

    public List<List<Integer>> levelOrder(TreeNode root) {
        if (root == null)
            return levels;
        helper(root, 0);
        return levels;
    }
    
    public static void main(String[] args) {
        TreeNode node_1 = new TreeNode(3);
        TreeNode node_2_l = new TreeNode(9);
        TreeNode node_2_r = new TreeNode(20);
        TreeNode node_3_r_l = new TreeNode(15);
        TreeNode node_3_r_r = new TreeNode(7);
        node_1.left=node_2_l;
        node_1.right=node_2_r;
        node_2_r.left=node_3_r_l;
        node_2_r.right=node_3_r_r;
        Solution solu = new Solution();
        solu.levelOrder(node_1);
    }

}

代码TreeNode

package binary_tree_level_order_traversal;

public class TreeNode {

     public int val;
     public TreeNode left;
     public TreeNode right;
     public TreeNode(int x) { val = x; }
}

方法 2：迭代

算法

上面的递归方法也可以写成迭代的形式。

我们将树上顶点按照层次依次放入队列结构中，队列中元素满足 FIFO（先进先出）的原则。在 Java 中可以使用 Queue 接口中的 LinkedList实现。在 Python 中如果使用 Queue 结构，但因为它是为多线程之间安全交换而设计的，所以使用了锁，会导致性能不佳。因此在 Python 中可以使用 deque 的 append() 和 popleft() 函数来快速实现队列的功能。

第 0 层只包含根节点 root ，算法实现如下：

初始化队列只包含一个节点 root 和层次编号 0 ： level = 0。
当队列非空的时候：
在输出结果 levels 中插入一个空列表，开始当前层的算法。
计算当前层有多少个元素：等于队列的长度。
将这些元素从队列中弹出，并加入 levels 当前层的空列表中。
将他们的孩子节点作为下一层压入队列中。
进入下一层 level++。

代码Solution

package binary_tree_level_order_traversal;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

public class Solution2 {
    
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> levels = new ArrayList<List<Integer>>();
        if (root == null)
            return levels;

        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        queue.add(root);
        int level = 0;
        while (!queue.isEmpty()) {
            // start the current level
            levels.add(new ArrayList<Integer>());

            // number of elements in the current level
            int level_length = queue.size();
            for (int i = 0; i < level_length; ++i) {
                TreeNode node = queue.remove();

                // fulfill the current level
                levels.get(level).add(node.val);

                // add child nodes of the current level
                // in the queue for the next level
                if (node.left != null)
                    queue.add(node.left);
                if (node.right != null)
                    queue.add(node.right);
            }
            // go to next level
            level++;
        }
        return levels;
    }

    public static void main(String[] args) {
        TreeNode node_1 = new TreeNode(3);
        TreeNode node_2_l = new TreeNode(9);
        TreeNode node_2_r = new TreeNode(20);
        TreeNode node_3_r_l = new TreeNode(15);
        TreeNode node_3_r_r = new TreeNode(7);
        node_1.left=node_2_l;
        node_1.right=node_2_r;
        node_2_r.left=node_3_r_l;
        node_2_r.right=node_3_r_r;
        Solution2 solu = new Solution2();
        solu.levelOrder(node_1);
    }
}