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

ภาพรวมปัญหา

ให้ต้นไม้ไบนารี ต้องการหาผลรวมของค่าใบ (leaf nodes) ที่เป็นลูกขวา (right child) ของ parent

ตัวอย่าง

ต้นไม้:

      3
     / \
    9   10
   / \
  15  7

ใบขวา: 7 (ลูกขวาของ 9), 10 (ลูกขวาของ 3) → ผลรวม = 17

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

1. ฟังก์ชัน dfs(node, isRightChild)
2. ถ้า node เป็นใบ (left==null && right==null) และ isRightChild==true → เพิ่มค่าในผลรวม
3. เรียก dfs(left, false) และ dfs(right, true)

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

#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 ret = 0;
    
    void dfs(TreeNode* node, bool isRight) {
        if (!node) return;
        if (!node->left && !node->right && isRight) {
            ret += node->val;
        }
        dfs(node->left, false);
        dfs(node->right, true);
    }
    
    int solve(TreeNode* root) {
        ret = 0;
        dfs(root, true); // root ถือว่าเป็น right child (ไม่ส่งผลเพราะไม่ใช่ leaf)
        return ret;
    }
};

int main() {
    Solution ob;
    TreeNode *root = new TreeNode(3);
    root->left = new TreeNode(9);
    root->right = new TreeNode(10);
    root->left->left = new TreeNode(15);
    root->left->right = new TreeNode(7);
    cout << ob.solve(root);
    return 0;
}

ผลลัพธ์

17

ความซับซ้อน

• เวลา: O(N) — เยี่ยมชมทุกโหนด 1 ครั้ง
• พื้นที่: O(H) — recursion stack

แนวทางอื่น: BFS

int sumRightLeaves_bfs(TreeNode* root) {
    if (!root) return 0;
    queue> q;
    q.push({root, false}); // root ไม่ใช่ right child
    int sum = 0;
    
    while (!q.empty()) {
        auto [node, isRight] = q.front(); q.pop();
        if (!node->left && !node->right && isRight) sum += node->val;
        if (node->left) q.push({node->left, false});
        if (node->right) q.push({node->right, true});
    }
    return sum;
}

ข้อสังเกต

• Root เองไม่ถูกนับแม้จะส่ง isRight=true เข้าไป เพราะ root ไม่ใช่ leaf
• เฉพาะ leaf node ที่เป็น right child เท่านั้นที่นับ