###### tags: `Leetcode` `easy` `tree` `bfs` `dfs` `python` `c++`

# 637. Average of Levels in Binary Tree

## [題目連結:] https://leetcode.com/problems/average-of-levels-in-binary-tree/

## 題目:
Given the ```root``` of a binary tree, return the average value of the nodes on each level in the form of an array. Answers within ```10**(-5)``` of the actual answer will be accepted.


#### [圖片來源:] https://leetcode.com/problems/average-of-levels-in-binary-tree/

## 解題想法:
* 題目為要求回傳紀錄每層的平均值
* BFS:
* 使用個que紀錄每層的node
* 一層一層計算

## Python:

class TreeNode(object):
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
    def insertLeft(self,node):
        if self.left==None:
            self.left=TreeNode(node)
        else:
            self.left.insertLeft(node)
    def insertRight(self,node):
        if self.right==None:
            self.right=TreeNode(node)
        else:
            self.right.insertRight(node)
    def printTree(self):
        root=self
        stack=[root]
        res=[]
        while stack:
            root=stack.pop(0)
            res.append(root.val)
            if root.left:
                stack.append(root.left)
            if root.right:
                stack.append(root.right)
        print(res)

class Solution(object):
    def averageOfLevels(self, root):
        """
        :type root: TreeNode
        :rtype: List[float]
        """
        res=[]
        que=[root] #當前que
        while que:
            nextLevel=[] #紀錄下層的node
            num=0 #當前層的node數量
            val=0 #當前層node.val總和
            for node in que:
                num+=1
                val+=float(node.val)
                if node.left:
                    nextLevel.append(node.left)
                if node.right:
                    nextLevel.append(node.right)
            res.append(val/num) #算平均
            que=nextLevel
        return res

if __name__=='__main__':
    root=TreeNode(3)
    root.insertLeft(9)
    root.insertRight(20)
    root.right.insertLeft(15)
    root.right.insertRight(7)
    root.printTree() #[3, 9, 20, 15, 7]

    result=Solution()
    ans=result.averageOfLevels(root)
    print(ans) #[3.0, 14.5, 11.0]

## C++:

#include<iostream>
#include<queue>
#include<vector>
using namespace std;

struct TreeNode{
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(): val(0), left(nullptr), right(nullptr){}
    TreeNode(int x): val(x), left(nullptr), right(nullptr){}
};

void InsertLeft(TreeNode* root, int data){
    TreeNode *tmp=root;
    if (tmp->left!=nullptr)
        InsertLeft(tmp->left,data);
    else{
        TreeNode *new_data= new TreeNode(data);
        tmp->left=new_data;
    }
}

void InsertRight(TreeNode* root, int data){
    TreeNode *tmp=root;
    if (tmp->right!=nullptr)
        InsertRight(tmp->right,data);
    else{
        TreeNode *new_data= new TreeNode(data);
        tmp->right=new_data;
    }
}

void PrintTree(TreeNode *root){
    TreeNode *tmp=root;
    queue<TreeNode*> que;
    vector<int> res;
    que.push(root);
    while (!que.empty()){
        TreeNode *root=que.front(); que.pop();
        res.push_back(root->val);
        if (root->left)
            que.push(root->left);
        if (root->right)
            que.push(root->right);
    }
    for (auto val: res){
        cout<<val<<" ";
    }
    cout<<endl;
}

class Solution {
public:
    vector<double> averageOfLevels(TreeNode* root) {
        vector<TreeNode*> que, nextLevel;
        vector<double> res;
        que.push_back(root);
        while (!que.empty()){
            double val=0; //count avg
            for (auto node: que){
                val+=node->val;
                if (node->left)
                    nextLevel.push_back(node->left);
                if (node->right)
                    nextLevel.push_back(node->right);
            }
            res.push_back(val/que.size()); //cal avg
            que.swap(nextLevel); //swap two vector let que get nextLevel
            nextLevel.clear(); //clear
        }
        return res;
    }
};

int main(){
    TreeNode *root=new TreeNode(3);
    InsertLeft(root,9);
    InsertRight(root,20);
    InsertLeft(root->left,15);
    InsertRight(root->right,7);
    PrintTree(root); //Original

    Solution res;
    vector<double> ans=res.averageOfLevels(root);
    for (auto val: ans){
        cout<<val<<" ";
    }
    cout<<endl;
    return 0;
}