# leetcode解題：(Medium) 102. Binary Tree Level Order Traversal

題目：[https://leetcode.com/problems/binary-tree-level-order-traversal/](https://leetcode.com/problems/binary-tree-level-order-traversal/)

描述：給定一棵樹的root，回傳以level order遍歷整棵樹的資料，且資料需要每層分開為一個List

解題思路：之前的遍歷(Preorder、Inorder、Postorder)都是屬於深度優先(Depth-First Search)的搜尋方式，Level order則是廣度優先(Breadth-first Search)的搜尋方式，遍歷時使用的資料結構從Stack改為Queue。這題因為需要每層分別為一個List，所以邏輯上需要在每一層遍歷完後就將該層的資料輸出、並將下一層的節點全部加入queue當中

程式碼：

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> result = new ArrayList<List<Integer>>();
        if(root == null) return result;

        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        queue.add(root);

        while(queue.peek() != null) {
            List<Integer> levelList = new ArrayList<Integer>();
            
            int levelLen = queue.size();
            for(int i = 0; i < levelLen; i++) {
                TreeNode node = queue.poll();
                if(node.left != null) queue.add(node.left);
                if(node.right != null) queue.add(node.right);
                levelList.add(node.val);
            }

            result.add(levelList);
        }

        return result;
    }
}

如果只需要照順序輸出不需分層的話程式會簡單許多：

class Solution {
    public List<Integer> preorder(Node root) {
        List<Integer> result = new ArrayList<Integer>();
        if(root == null) return result;

        Queue<Node> queue = new LinkedList<Node>();
        queue.add(root);

        while(queue.peek() != null) {
            Node top = queue.poll();
            result.add(top.val);

            for(Node child : top.children) {
                queue.add(child);
            }
        }

        return result;
    }
}

時間複雜度：O(n)
空間複雜度：O(n)

###### tags: `leetcode` `medium` `binary tree` `BFS`