Home Computer Science Java Algorithm

69 · Binary Tree Level Order Traversal - LintCode

# Description

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

# Example

Example 1:

Input:

tree = {1,2,3}

Output:

[[1],[2,3]]

Explanation:

   1 
  / \ 
 2   3

it will be serialized {1,2,3}
Example 2:

Input:

tree = {1,#,2,3}

Output:

[[1],[2],[3]]

# Solution

copy from leetcode:
题目要求我们一层一层输出树的结点的值，很明显需要使用「广度优先遍历」实现；

广度优先遍历借助「队列」实现；

注意：

这样写 for (int i = 0; i < queue.size(); i++) { 代码是不能通过测评的，这是因为 queue.size() 在循环中是变量（这条规则在 Python 中不成立，请各位读者自行验证）。正确的做法是：每一次在队列中取出元素的个数须要先暂存起来，请见参考代码；
子结点入队的时候，非空的判断很重要：在队列的队首元素出队的时候，一定要在左（右）子结点非空的时候才将左（右）子结点入队。
树的广度优先遍历的写法模式相对固定：

使用队列；
在队列非空的时候，动态取出队首元素；
取出队首元素的时候，把队首元素相邻的结点（非空）加入队列。


-   时间复杂度：O(N)O(N)，这里 NN 是二叉树结点的个数，每个结点都访问一次，因此时间复杂度是 O(N)O(N)；
-   空间复杂度：O(N)O(N)。

/**
 * Definition of TreeNode:
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left, right;
 *     public TreeNode(int val) {
 *         this.val = val;
 *         this.left = this.right = null;
 *     }
 * }
 */
public class Solution {
    /**
     * @param root: A Tree
     * @return: Level order a list of lists of integer
     */
    public List<List<Integer>> levelOrder(TreeNode root) {
	    // 注意返回值
       List result = new ArrayList<>();
       if (root == null) return result;
     
       Queue<TreeNode> queue = new LinkedList<>();
       //step 1：把 root 放進隊列
       queue.offer(root);
       while (!queue.isEmpty()){
       //ArrayList 一定要在 while loop 裡建新，因為每次 level 都不一樣
           List<Integer> level = new ArrayList<>();
           // 取 Queue size，因為每一層都有不同的 node
           // 把 size 放這裡，而不是 for loop 裡是因為會在 loop 裡放 node 的孩子，size 是變量
           int size = queue.size();
          // 遍歷 queue，樹的每一層
           for (int i = 0; i < size; i++){
            //poll 出來一個，看當前節點有沒有孩子，若有，就把它放到 queue
                TreeNode node = queue.poll();
                // 把當前的 node.val 記下來
                level.add(node.val);
               if (node.left != null){
                   queue.offer(node.left);
               } 
               if (node.right != null){
                   queue.offer(node.right);
               }
           }
           
        result.add(level);
       }
  
       return result;
    }
}