13.3 層次遍歷

我們可以使用廣度優先搜尋進行層次遍歷。注意，不需要使用兩個佇列來分別儲存當前層的節點和下一層的節點，因為在開始遍歷一層節點時，當前佇列中的節點數就是當前層的節點數，只要控制遍歷這麼多節點數，就能保證這次遍歷的都是當前層的節點。

637. Average of Levels in Binary Tree

題目描述

給定一個二元樹，求每一層的節點值的平均數。

輸入輸出範例

輸入是一個二元樹，輸出是一個一維陣列，表示每層節點值的平均數。

Input:
    3
   / \
  9  20
     / \
    15  7
Output: [3, 14.5, 11]

題解

利用廣度優先搜尋，我們可以很方便地求取每層的平均值。

C++

vector<double> averageOfLevels(TreeNode* root) {
    vector<double> level_avg;
    if (root == nullptr) {
        return level_avg;
    }
    queue<TreeNode*> q;
    q.push(root);
    int count = q.size();
    while (count > 0) {
        double level_sum = 0;
        for (int i = 0; i < count; ++i) {
            TreeNode* node = q.front();
            q.pop();
            level_sum += node->val;
            if (node->left != nullptr) {
                q.push(node->left);
            }
            if (node->right != nullptr) {
                q.push(node->right);
            }
        }
        level_avg.push_back(level_sum / count);
        count = q.size();
    }
    return level_avg;
}

Python

def averageOfLevels(root: Optional[TreeNode]) -> List[float]:
    level_avg = []
    if root is None:
        return level_avg
    q = collections.deque()
    q.append(root)
    count = len(q)
    while count > 0:
        level_sum = 0
        for _ in range(count):
            node = q.popleft()
            level_sum += node.val
            if node.left is not None:
                q.append(node.left)
            if node.right is not None:
                q.append(node.right)
        level_avg.append(level_sum / count)
        count = len(q)
    return level_avg