ผลรวมระดับสูงสุดของต้นไม้แบบทวิภาคใน C++

สมมติว่าเรามีรากของต้นไม้แบบทวิภาค ระดับของรากคือ 1 ลูกคือ 2 ไปเรื่อยๆ ต้องคืนระดับ X ที่เล็กที่สุด ที่ผลรวมค่าโหนดในระดับนั้นเป็นค่าสูงสุด

ตัวอย่าง ต้นไม้ดังภาพ ผลลัพธ์: 2

ระดับ 1 ผลรวม = 1, ระดับ 2 ผลรวม = 7 + 0 = 7, ระดับ 3 ผลรวม = 7 + (-8) = -1 ดังนั้นระดับ 2 สูงสุด

ขั้นตอนการแก้ปัญหา (BFS Level Order Traversal)

• level := 1, sum := ค่าของ r, ansLevel := level, ansSum := sum
• กำหนดคิว q ใส่โหนด r
• while q ไม่ว่าง:
  • capacity := ขนาดของ q
  • เพิ่ม level ขึ้น 1, sum := 0
  • while capacity ไม่ใช่ 0:
    • node := โหนดหน้าของ q ลบออก
    • ถ้าลูกขวาของ node มีอยู่: sum += ค่าลูกขวา ใส่ลูกขวาเข้า q
    • ถ้าลูกซ้ายของ node มีอยู่: sum += ค่าลูกซ้าย ใส่ลูกซ้ายเข้า q
    • ลด capacity ลง 1
  • ถ้า ansSum < sum: ansSum := sum, ansLevel := level
• คืน ansLevel

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

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

class TreeNode {
public:
    int val;
    TreeNode *left, *right;
    TreeNode(int data) {
        val = data;
        left = NULL;
        right = NULL;
    }
};

void insert(TreeNode **root, int val) {
    queue<TreeNode*> q;
    q.push(*root);
    while(q.size()) {
        TreeNode *temp = q.front();
        q.pop();
        if(!temp->left) {
            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; i < v.size(); i++) {
        insert(&root, v[i]);
    }
    return root;
}

class Solution {
public:
    int maxLevelSum(TreeNode* r) {
        int level = 1, sum = r->val;
        int ansLevel = level, ansSum = sum;
        queue <TreeNode*> q;
        q.push(r);
        while(!q.empty()) {
            int capacity = q.size();
            level++;
            sum = 0;
            while(capacity--) {
                TreeNode* node = q.front();
                q.pop();
                if(node->right) {
                    sum += node->right->val;
                    q.push(node->right);
                }
                if(node->left) {
                    sum += node->left->val;
                    q.push(node->left);
                }
            }
            if(ansSum < sum) {
                ansSum = sum;
                ansLevel = level;
            }
        }
        return ansLevel;
    }
};

int main() {
    vector<int> v = {1,7,0,7,-8,NULL,NULL};
    TreeNode *root = make_tree(v);
    Solution ob;
    cout << ob.maxLevelSum(root);
}

อินพุต

[1,7,0,7,-8,null,null]

เอาต์พุต

2