โปรแกรมหาผลรวมของโหนดลึกที่สุดในต้นไม้ไบนารีใน C++

ภาพรวมปัญหา

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

ตัวอย่าง

ต้นไม้:

       1
      / \
     2   3
    / \   \
   4   5   6
  /         \
 7           4

โหนดลึกที่สุด (depth 3): 7 และ 4 → ผลรวม = 11

แนวทางแก้ปัญหา (DFS + Map)

1. ใช้ map เก็บผลรวมค่าโหนดแต่ละ depth: depth → sum
2. DFS traversal พร้อมส่ง parameter depth
3. อัปเดต maxDepth และ m[depth] += node->val
4. คืนค่า m[maxDepth]

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

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

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

class Solution {
public:
    int maxDepth = 0;
    map m;
    
    void solve(TreeNode* node, int level = 0) {
        if (!node) return;
        maxDepth = max(maxDepth, level);
        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() {
    TreeNode *root = new TreeNode(1);
    root->left = new TreeNode(2);
    root->right = new TreeNode(3);
    root->left->left = new TreeNode(4);
    root->left->right = new TreeNode(5);
    root->right->right = new TreeNode(6);
    root->right->right->right = new TreeNode(4);
    root->left->left->left = new TreeNode(7);
    
    Solution ob;
    cout << ob.deepestLeavesSum(root);
    return 0;
}

ผลลัพธ์

11

แนวทางอื่น: BFS (Level Order Traversal)

ใช้ Queue ทำ BFS ระดับต่อระดับ ผลรวมระดับสุดท้ายคือคำตอบ

int deepestLeavesSum_bfs(TreeNode* root) {
    if (!root) return 0;
    queue q;
    q.push(root);
    int sum = 0;
    
    while (!q.empty()) {
        int sz = q.size();
        sum = 0;
        for (int i = 0; i < sz; i++) {
            TreeNode* node = q.front(); q.pop();
            sum += node->val;
            if (node->left) q.push(node->left);
            if (node->right) q.push(node->right);
        }
    }
    return sum; // sum ของระดับสุดท้าย
}

ความซับซ้อน

ข้อดีของ BFS

• ไม่ต้องใช้ recursion (หลีกเลี่ยง stack overflow)
• เข้าใจง่าย ไม่ต้องเก็บ map ทุก depth
• พื้นที่ O(W) ซึ่งสำหรับ balanced tree W ≈ N/2 แต่อาจดีกว่า H สำหรับ skewed tree

โปรแกรมหาชื่อคอลัมน์สเปรดชีตจากหมายเลขคอลัมน์ใน C++

โปรแกรมหาผลรวมของใบขวาในต้นไม้ไบนารีใน C++