Tìm tổng của tất cả các lá bên phải trong Cây nhị phân đã cho trong C ++

Trong bài toán này, chúng ta được đưa ra một cây nhị phân. Nhiệm vụ của chúng ta là tìm tổng của tất cả bên trái trong Cây nhị phân đã cho .

Hãy lấy một ví dụ để hiểu vấn đề,

Đầu vào:

Đầu ra:8

Giải thích -

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

Phương pháp tiếp cận giải pháp

Một giải pháp đơn giản cho vấn đề này là cắt ngang cây từ gốc đến lá. Nếu một nút là nút lá bên trái, hãy cộng nó thành tổng. Khi toàn bộ cây được đi ngang. In Tổng.

Ví dụ

Chương trình minh họa hoạt động của giải pháp của chúng tôi

#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;
}

đầu ra

The sum of right leaves of the tree is 8

Một cách tiếp cận khác sử dụng Lặp lại

Chúng tôi sẽ thực hiện duyệt tìm kiếm theo độ sâu đầu tiên trên cây, và sau đó kiểm tra xem nút hiện tại có phải là lá bên phải hay không. Nếu Có, hãy cộng giá trị của nó thành tổng, Nếu không, bỏ đi. Ở cuối, hãy in tổng.

Ví dụ

Chương trình minh họa hoạt động của giải pháp của chúng tôi

#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;
}

Đầu ra

The sum of right leaves of the tree is 8

Phương pháp tiếp cận 3, sử dụng BFS

Chúng tôi sẽ thực hiện tìm kiếm theo chiều rộng đầu tiên với một biến để chỉ ra liệu nút có phải là nút con bên phải hay không. Nếu đúng, hãy cộng nó vào tổng, nếu không thì bỏ đi. Ở cuối, in tổng.

Ví dụ

Chương trình minh họa hoạt động của giải pháp của chúng tôi

#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;
}

Đầu ra

The sum of right leaves of the tree is 8