C++에서 주어진 이진 트리의 모든 왼쪽 잎의 합 찾기

이 문제에서는 이진 트리가 제공됩니다. 우리의 임무는 주어진 이진 트리에서 모든 왼쪽 잎의 합을 찾는 것입니다. .

문제를 이해하기 위해 예를 들어 보겠습니다.

입력:

출력 :11

설명 -

All leaf nodes of the tree are : 2, 9
Sum = 2 + 9 = 11

솔루션 접근 방식

이 문제에 대한 간단한 해결책은 루트에서 리프로 트리를 탐색하는 것입니다. 노드가 왼쪽 리프 노드인 경우 합계에 추가합니다. 전체 트리를 횡단할 때. 합계 인쇄.

예시

솔루션 작동을 설명하는 프로그램

#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

반복을 사용한 또 다른 접근 방식

트리에서 깊이 우선 탐색 탐색을 수행한 다음 현재 노드가 왼쪽 잎인지 확인합니다. 예인 경우 합계에 값을 추가하고, 그렇지 않으면 그대로 두십시오. 마지막에 합계를 출력합니다.

예시

솔루션 작동을 설명하는 프로그램

#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 사용

노드가 왼쪽 자식인지 여부를 나타내기 위해 변수를 사용하여 너비 우선 검색을 수행합니다. 그렇다면 합계에 더하고 그렇지 않으면 그대로 두십시오. 마지막에 합계를 출력합니다.

예시

솔루션 작동을 설명하는 프로그램

#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