หาผลรวมของใบไม้ซ้ายทั้งหมดใน Binary Tree ด้วย C++

ในปัญหานี้ เราได้รับ Binary Tree งานของเราคือ การหาผลรวมของใบไม้ซ้ายทั้งหมด ใน Binary Tree นั้น

ตัวอย่างเพื่อความเข้าใจ

Input (โครงสร้างต้นไม้):

Output : 11

คำอธิบาย

ใบไม้ทั้งหมดของต้นไม้คือ: 2, 9
ผลรวม = 2 + 9 = 11

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

วิธีแก้ที่ง่ายคือการเดินผ่านต้นไม้จากราก (root) ไปยังใบไม้ (leaf) หากโหนดเป็นใบไม้ซ้าย ให้บวกค่าลงในผลรวม เมื่อเดินครบทุกโหนดแล้ว ให้พิมพ์ผลรวม

วิธีที่ 1: ใช้ Recursion (เวียนเกิด)

#include <iostream>
using namespace std;

struct Node {
    int key;
    struct Node* left, *right;
};

Node* newNode(char k) {
    Node* node = new Node;
    node->key = k;
    node->right = node->left = NULL;
    return node;
}

bool isLeafNode(Node* node) {
    if (node == NULL)
        return false;
    if (node->left == NULL && node->right == NULL)
        return true;
    return false;
}

int findLeftLeavesSum(Node* root) {
    int sum = 0;
    if (root != NULL) {
        if (isLeafNode(root->left))
            sum += root->left->key;
        else
            sum += findLeftLeavesSum(root->left);
        sum += findLeftLeavesSum(root->right);
    }
    return sum;
}

int main() {
    struct Node* root = newNode(5);
    root->left = newNode(4);
    root->right = newNode(6);
    root->left->left = newNode(2);
    root->left->right = newNode(1);
    root->right->left = newNode(9);
    root->right->right = newNode(7);
    cout << "The sum of left leaves of the tree is " << findLeftLeavesSum(root);
    return 0;
}

ผลลัพธ์

The sum of left leaves of the tree is 11

วิธีที่ 2: ใช้ Iteration (DFS ด้วย Stack)

เราจะทำการท่องต้นไม้แบบ Depth First Search โดยใช้ Stack ตรวจสอบว่าโหนดปัจจุบันเป็นใบไม้ซ้ายหรือไม่ ถ้าใช่ บวกค่าเข้าไปในผลรวม

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

struct Node {
    int key;
    struct Node* left, *right;
};

Node* newNode(char k) {
    Node* node = new Node;
    node->key = k;
    node->right = node->left = NULL;
    return node;
}

int findLeftLeavesSum(Node* root) {
    if (root == NULL)
        return 0;
    
    stack<Node*> treeNodes;
    treeNodes.push(root);
    int sum = 0;
    
    while (treeNodes.size() > 0) {
        Node* currentNode = treeNodes.top();
        treeNodes.pop();
        
        if (currentNode->left != NULL) {
            treeNodes.push(currentNode->left);
            if (currentNode->left->left == NULL && 
                currentNode->left->right == NULL) {
                sum += currentNode->left->key;
            }
        }
        if (currentNode->right != NULL)
            treeNodes.push(currentNode->right);
    }
    return sum;
}

int main() {
    Node* root = newNode(5);
    root->left = newNode(4);
    root->right = newNode(6);
    root->left->left = newNode(2);
    root->left->right = newNode(1);
    root->right->left = newNode(9);
    root->right->right = newNode(7);
    cout << "The sum of left leaves of the tree is " << findLeftLeavesSum(root);
    return 0;
}

ผลลัพธ์

The sum of left leaves of the tree is 11

วิธีที่ 3: ใช้ BFS (Breadth First Search)

ใช้การค้นหาแบบกว้าง (BFS) พร้อมตัวแปรบอกว่าโหนดนั้นเป็นลูกซ้ายหรือไม่ หากเป็น ให้บวกเข้าไปในผลรวม

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

struct Node {
    int key;
    struct Node* left, *right;
};

Node* newNode(char k) {
    Node* node = new Node;
    node->key = k;
    node->right = node->left = NULL;
    return node;
}

int findLeftLeavesSum(Node* root) {
    if (root == NULL)
        return 0;
    
    queue<pair<Node*, bool> > leftTreeNodes;
    leftTreeNodes.push({ root, 0 });
    int sum = 0;
    
    while (!leftTreeNodes.empty()) {
        Node* temp = leftTreeNodes.front().first;
        bool is_left_child = leftTreeNodes.front().second;
        leftTreeNodes.pop();
        
        if (!temp->left && !temp->right && is_left_child)
            sum = sum + temp->key;
        
        if (temp->left) {
            leftTreeNodes.push({ temp->left, 1 });
        }
        if (temp->right) {
            leftTreeNodes.push({ temp->right, 0 });
        }
    }
    return sum;
}

int main() {
    Node* root = newNode(5);
    root->left = newNode(4);
    root->right = newNode(6);
    root->left->left = newNode(2);
    root->left->right = newNode(1);
    root->right->left = newNode(9);
    root->right->right = newNode(7);
    cout << "The sum of left leaves of the tree is " << findLeftLeavesSum(root);
    return 0;
}

ผลลัพธ์

The sum of left leaves of the tree is 11