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