Tìm tổng các node lá bên trái của cây nhị phân trong C++

Cho cây nhị phân, tính tổng các node lá (leaf) nằm bên trái của node cha.

Ví dụ

Output: 15

Giải thích: Các node lá bên trái: 9, 4, 2 → Tổng = 15.

Cách tiếp cận: Đệ quy

• Hàm leftLeafSum(root) trả về tổng
• Base case: root NULL → 0
• Nếu root->left là leaf (không có con) → cộng root->left->data + đệ quy right
• Ngược lại → đệ quy left + đệ quy right

Code C++

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

struct treenode {
    int data;
    treenode* left;
    treenode* right;
};

struct treenode* createNode(int d) {
    struct treenode* root = new treenode;
    root->data = d; root->left = NULL; root->right = NULL;
    return root;
}

int leftLeafSum(treenode* root) {
    if (!root) return 0;
    if (root->left && !root->left->left && !root->left->right)
        return root->left->data + leftLeafSum(root->right);
    return leftLeafSum(root->left) + leftLeafSum(root->right);
}

int main() {
    struct treenode* root = NULL;
    root = createNode(4);
    root->left = createNode(2);
    root->right = createNode(2);
    root->left->right = createNode(7);
    root->left->left = createNode(5);
    root->right->left = createNode(5);
    root->right->right = createNode(7);
    cout << leftLeafSum(root) << endl;
    return 0;
}

Kết quả

10

Node lá bên trái: 5 và 5 → Tổng = 10.