ค้นหาผลรวมของใบไม้ที่ถูกต้องใน Binary Tree ที่กำหนดใน C++

ในปัญหานี้ เราได้รับไบนารีทรี งานของเราคือ หาผลรวมของทั้งหมดทางขวาในต้นไม้ไบนารีที่กำหนด .

มาดูตัวอย่างเพื่อทำความเข้าใจปัญหากัน

ข้อมูลเข้า :

เอาท์พุต :8

คำอธิบาย −

All leaf nodes of the tree are : 1, 8
Sum = 1 + 8 = 9

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

วิธีแก้ปัญหาง่ายๆ คือการสำรวจต้นไม้จากรากหนึ่งไปยังอีกใบหนึ่ง หากโหนดเป็นโหนดปลายด้านซ้าย ให้เพิ่มลงในผลรวม เมื่อข้ามต้นไม้ทั้งต้น พิมพ์ผลรวม

ตัวอย่าง

โปรแกรมเพื่อแสดงการทำงานของโซลูชันของเรา

#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 findRightLeavesSum(Node *root){
   int sum = 0;
   if (root != NULL){
      if (isLeafNode(root->right))
         sum += root->right->key;
      else
         sum += findRightLeavesSum(root->right);
      sum += findRightLeavesSum(root->left);
   }
   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 right leaves of the tree is "<<findRightLeavesSum(root);
   return 0;
}

ผลลัพธ์

The sum of right leaves of the tree is 8

แนวทางอื่นโดยใช้การวนซ้ำ

เราจะทำการค้นหาเชิงลึกก่อนข้ามผ่านต้นไม้ จากนั้นตรวจสอบว่าโหนดปัจจุบันเป็นใบไม้ที่ถูกต้องหรือไม่ ถ้าใช่ ให้เพิ่มมูลค่าเป็นผลรวม มิฉะนั้น ให้ปล่อย ในตอนท้ายพิมพ์ผลรวม

ตัวอย่าง

โปรแกรมเพื่อแสดงการทำงานของโซลูชันของเรา

#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 findRightLeavesSum(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->right != NULL){
         treeNodes.push(currentNode->right);
         if(currentNode->right->right == NULL &&
            currentNode->right->left == NULL){
            sum += currentNode->right->key ;
         }
      }
      if (currentNode->left != NULL)
         treeNodes.push(currentNode->left);
   }
   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 right leaves of the tree is "<<findRightLeavesSum(root);
   return 0;
}

ผลลัพธ์

The sum of right leaves of the tree is 8

วิธีที่ 3 โดยใช้ 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 findRightLeavesSum(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, 0 });
      }
      if (temp->right) {
         leftTreeNodes.push({ temp->right, 1 });
      }
   }
   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 right leaves of the tree is "<<findRightLeavesSum(root);
   return 0;
}

ผลลัพธ์

The sum of right leaves of the tree is 8