หาผลรวม Left Leaf Nodes ของ Binary Tree ใน C++

โจทย์

กำหนด Binary Tree หาผลรวมของ Leaf Nodes ที่เป็น Left Child ของ Parent (Left Leaves)

ตัวอย่าง

       4
      / \
     2   2
    / \ / \
   5  7 5  7
Left Leaves: 5 (left of 2), 5 (left of 2) → Sum = 10

แนวคิด: Recursive DFS

Traverse Tree ตรวจสอบแต่ละโหนด: ถ้า node->left มีอยู่ และ node->left เป็น Leaf (ไม่มีลูก) → บวกค่า node->left->val

โค้ด C++

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

struct TreeNode {
    int val;
    TreeNode *left, *right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

int sumOfLeftLeaves(TreeNode* root) {
    if (!root) return 0;
    
    int sum = 0;
    
    // ตรวจสอบ Left Child ของ Root ปัจจุบัน
    if (root->left && !root->left->left && !root->left->right) {
        sum += root->left->val; // Left Leaf!
    }
    
    // Recurse ทั้งซ้ายและขวา
    sum += sumOfLeftLeaves(root->left);
    sum += sumOfLeftLeaves(root->right);
    
    return sum;
}

// Alternative: Helper with flag
int sumLeftLeavesHelper(TreeNode* node, bool isLeft) {
    if (!node) return 0;
    if (!node->left && !node->right) { // Leaf
        return isLeft ? node->val : 0;
    }
    return sumLeftLeavesHelper(node->left, true) + 
           sumLeftLeavesHelper(node->right, false);
}

int sumOfLeftLeaves2(TreeNode* root) {
    return sumLeftLeavesHelper(root, false);
}

// Helper สร้าง Tree
TreeNode* createNode(int val) {
    return new TreeNode(val);
}

int main() {
    //       4
    //      / \
    //     2   2
    //    / \ / \
    //   5  7 5  7
    TreeNode* root = createNode(4);
    root->left = createNode(2);
    root->right = createNode(2);
    root->left->left = createNode(5);
    root->left->right = createNode(7);
    root->right->left = createNode(5);
    root->right->right = createNode(7);
    
    cout << "Sum of Left Leaves: " << sumOfLeftLeaves(root) << endl; // 10
    cout << "Method 2: " << sumOfLeftLeaves2(root) << endl; // 10
    
    // Test: Single node
    TreeNode* single = createNode(1);
    cout << "Single node: " << sumOfLeftLeaves(single) << endl; // 0
    
    // Test: Only right children
    TreeNode* rightOnly = createNode(1);
    rightOnly->right = createNode(2);
    rightOnly->right->right = createNode(3);
    cout << "Right only: " << sumOfLeftLeaves(rightOnly) << endl; // 0
    
    return 0;
}

Complexity

• Time: O(n) - Visit every node once
• Space: O(h) - Recursion stack (h = height)

Iterative Version (Stack)

int sumOfLeftLeavesIterative(TreeNode* root) {
    if (!root) return 0;
    int sum = 0;
    stack<pair<TreeNode*, bool>> st; // node, isLeft
    st.push({root, false});
    
    while (!st.empty()) {
        auto [node, isLeft] = st.top(); st.pop();
        if (!node->left && !node->right) {
            if (isLeft) sum += node->val;
        } else {
            if (node->right) st.push({node->right, false});
            if (node->left) st.push({node->left, true});
        }
    }
    return sum;
}

ผลลัพธ์

Sum of Left Leaves: 10
Method 2: 10
Single node: 0
Right only: 0

สรุป

Sum of Left Leaves = DFS ตรวจสอบว่า Node เป็น Left Child และเป็น Leaf พร้อมกัน 2 วิธี: (1) Check parent's left child (2) Pass flag isLeft - LeetCode 404