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

루트 노드와 왼쪽 자식 및 오른쪽 자식이 있는 이진 트리가 있다고 가정해 보겠습니다. 작업은 부모 노드에 남겨진 트리의 잎 노드의 총합을 찾는 것입니다.

예를 들어

입력-1:

<강한>

출력:

15

설명: 주어진 입력 Binary Tree에서 모든 왼쪽 잎 노드의 합은 9+4+2 =15입니다. 따라서 출력은 15입니다.

이 문제를 해결하기 위한 접근 방식

Binary Tree가 있고 작업은 부모에게 남겨진 모든 잎 노드의 합을 찾는 것입니다.

이 문제를 해결하기 위한 재귀적 접근 방식은 루트 노드의 왼쪽 노드가 비어 있는지 확인하는 것입니다. 비어 있으면 왼쪽 노드의 합계를 계산하고 오른쪽 노드의 재귀 합계를 찾습니다. 따라서 모든 노드에 대해 재귀적으로 확인하고 합을 찾습니다.

• 루트 노드와 왼쪽 자식과 오른쪽 자식을 입력으로 갖는 이진 트리를 가져옵니다.
• 정수 함수 leftLeafSum(treenode*root)은 루트 노드를 입력으로 사용하고 부모에게 남겨진 모든 리프 노드의 합계를 반환합니다.
• 루트 노드가 비어 있거나 NULL이면 '0'을 반환하고 그렇지 않으면 루트 노드의 왼쪽 노드를 확인합니다.
• 루트 노드의 왼쪽 노드에 자식이 없으면 오른쪽 노드를 재귀적으로 확인합니다.
• 왼쪽 자식과 오른쪽 자식에 대해 재귀적으로 합계를 반환합니다.

예시

#include<bits/stdc++.h>
using namespace std;
struct treenode {
   int data;
   treenode * left;
   treenode * right;
};
struct treenode * createNode(int d) {
   struct treenode * root = new treenode;
   root -> data = d;
   root -> left = NULL;
   root -> right = NULL;
   return root;
}
int leftLeafSum(treenode * root) {
   if (root == NULL) {
      return 0;
   }
   if (root -> left and!root -> left -> left and!root -> left -> right) {
      return root -> left -> data + leftLeafSum(root -> right);
   }
   return leftLeafSum(root -> left) + leftLeafSum(root -> right);
}
int main() {
   struct treenode * root = NULL;
   root = createNode(4);
   root -> left = createNode(2);
   root -> right = createNode(2);
   root -> left -> right = createNode(7);
   root -> left -> left = createNode(5);
   root -> right -> left = createNode(5);
   root -> right -> right = createNode(7);
   int sum = leftLeafSum(root);
   cout << sum << endl;
   return 0;
}

위의 코드를 실행하면 출력이 다음과 같이 생성됩니다.

출력

10

설명: 왼쪽 노드의 리프 노드는 5와 5로 부모에게 남아 있으므로 모든 리프 노드의 합계는 =10입니다.