ผลรวมใบลึกที่สุดใน C++

สมมติว่าเรามีต้นไม้แบบทวิภาค เราต้องหาผลรวมของค่าใบลึกที่สุด (deepest leaves)

ตัวอย่าง ต้นไม้ดังภาพ:

ผลลัพธ์: 15

ขั้นตอนการแก้ปัญหา (DFS + Map)

• กำหนดแผนที่ m และ maxDepth
• กำหนดเมธอดเวียนเกิด solve() รับ node และ level (เริ่มต้น 0)
• ถ้า node ไม่มีอยู่ ให้คืนค่า
• maxDepth := max(level, maxDepth)
• เพิ่ม m[level] ด้วยค่าของ node
• เรียก solve(left of node, level + 1)
• เรียก solve(right of node, level + 1)
• ในเมธอดหลัก กำหนด maxDepth := 0 เรียก solve(root, 0)
• คืนค่า m[maxDepth]

ตัวอย่างโค้ด (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 maxDepth;
    map <int, int> m;
    void solve(TreeNode* node, int level = 0) {
        if(!node) return;
        maxDepth = max(level, maxDepth);
        m[level] += node->val;
        solve(node->left, level + 1);
        solve(node->right, level + 1);
    }
    int deepestLeavesSum(TreeNode* root) {
        maxDepth = 0;
        m.clear();
        solve(root);
        return m[maxDepth];
    }
};

int main() {
    vector<int> v = {1,2,3,4,5,NULL,6,7,NULL,NULL,NULL,NULL,8};
    TreeNode *root = make_tree(v);
    Solution ob;
    cout << (ob.deepestLeavesSum(root));
}

อินพุต

[1,2,3,4,5,null,6,7,null,null,null,null,8]

เอาต์พุต

15