#102. Binary Tree Level Order Traversal

題目描述

給你一個二元樹的根結點root，按照階層回傳節點值(每一層從左到右排序)。

限制條件

節點數量[0, 2000]。
-1000 <= 節點值 <= 1000。
每一層從左到右排序

解題思路

節點按照每一層由左至右顯示，所以順序會是「第一層左到右」、「第二層左到右」、「第三層左到右」。在處理第一層的時候，需要先儲存下一層的節點，按照由左至右的順序排列，輪到下一層時，儲存更下一層的節點，以此類推。這個時候儲存的方法，我們可以使用佇列Queue來進行，Queue的特性是先進先出(FIFO)，因此在儲存節點的時候，由左至右儲存，取出的時候也是由左至右取出。這種方式也被稱做寬度優先搜尋(Breadth-First Search,BFS)。

Breadth-First Search

public class Solution {
    public IList<IList<int>> LevelOrder(TreeNode root) {
        if(root==null) return new List<IList<int>>();
        List<IList<int>> ans = new List<IList<int>>();
        Queue<TreeNode> q = new Queue<TreeNode>();
        q.Enqueue(root);        
        while(q.Count!=0){
            int len = q.Count;
            List<int> tmp = new List<int>();
            for(int i=0;i<len;i++){
                TreeNode qc = q.Dequeue();
                tmp.Add(qc.val);
                if(qc.left!=null) q.Enqueue(qc.left);
                if(qc.right!=null) q.Enqueue(qc.right);
            }
            ans.Add(tmp);
        }
        return ans;
    }
}

複雜度分析：

時間複雜度：要檢查完所有節點，因此時間複雜度為O(n)。
空間複雜度：最壞的情況下，Queue占用的空間大小會是最底層的節點數量，也就是2ⁿ，n為樹的層數，空間複雜度為O(2ⁿ)。

學習重點

寬度優先搜尋(Breadth-First Search,BFS)。