ค่าเฉลี่ยของแต่ละระดับใน Binary Tree ใน C++

ปัญหา

สมมติว่าเรามี binary tree ที่ไม่ว่างเปล่า เราต้องหาค่าเฉลี่ยของโหนดในแต่ละระดับ และคืนค่าค่าเฉลี่ยเป็นอาร์เรย์

เช่น ถ้าผนวกเข้าเป็น (รูปภาพต้นไม้) ผลลัพธ์จะเป็น [3, 14.5, 11]

วิธีแก้ปัญหา

1. กำหนดอาร์เรย์ result
2. กำหนดคิว q หนึ่งอัน
3. เพิ่ม root เข้า q
4. while (q ไม่ว่าง) ทำ:
   • n := ขนาดของ q
   • กำหนดอาร์เรย์ temp
   • while n ไม่เท่ากับ 0 ทำ:
     • t := สมาชิกแรกของ q
     • เพิ่มค่าของ t เข้า temp
     • ลบสมาชิกออกจาก q
     • ถ้า left of t ไม่เป็น null: เพิ่ม left of t เข้า q
     • ถ้า right of t ไม่เป็น null: เพิ่ม right of t เข้า q
     • ลด n ลง 1
   • ถ้าขนาดของ temp เท่ากับ 1: เพิ่ม temp[0] เข้า result
   • มิฉะนั้นถ้าขนาดของ temp > 1:
     • sum := 0
     • for i := 0 ถึง ขนาดของ temp - 1 ทำ: sum := sum + temp[i]
     • เพิ่ม (sum / ขนาดของ temp) เข้า result
5. คืนค่า result

ตัวอย่างโค้ด C++

#include <bits/stdc++.h> 
using namespace std; 

void print_vector(vector<auto> v){ 
    cout << "["; 
    for(int i = 0; ileft){ 
            if(val != NULL) 
                temp->left = new TreeNode(val); 
            else 
                temp->left = new TreeNode(0); 
            return; 
        } else{ 
            q.push(temp->left); 
        } 
        if(!temp->right){ 
            if(val != NULL) 
                temp->right = new TreeNode(val); 
            else 
                temp->right = new TreeNode(0); 
            return; 
        } else{ 
            q.push(temp->right); 
        } 
    } 
} 

TreeNode *make_tree(vector<int> v){ 
    TreeNode *root = new TreeNode(v[0]); 
    for(int i = 1; ival); 
                q.pop(); 
                if (t->left && t->left->val != 0) 
                    q.push(t->left); 
                if (t->right && t->right->val != 0) 
                    q.push(t->right); 
                n--; 
            } 
            if (temp.size() == 1) 
                result.push_back(temp[0]); 
            else if (temp.size() > 1) { 
                double sum = 0; 
                for (int i = 0; i < temp.size(); i++) { 
                    sum += temp[i]; 
                } 
                result.push_back(sum / temp.size()); 
            } 
        } 
        return result; 
    } 
}; 

int main(){ 
    Solution ob; 
    vector<int> v = {3,9,20,NULL,NULL,15,7}; 
    TreeNode *root = make_tree(v); 
    print_vector(ob.averageOfLevels(root)); 
}

อินพุต

{3,9,20,NULL,NULL,15,7}

เอาต์พุต

[3, 14.5, 11, ]