C++의 이진 트리에서 가장 깊은 왼쪽 리프 노드

이 튜토리얼에서는 바이너리 트리에서 가장 깊은 왼쪽 리프 노드를 찾을 것입니다. 바이너리 트리를 보자.

   A
      B    C
D       E       F
                     G

문제를 해결하는 단계를 살펴보겠습니다.

• char, 왼쪽 및 오른쪽 포인터를 사용하여 Node 구조체를 작성합니다.

• 더미 데이터로 바이너리 트리를 초기화합니다.

• 이진 함수에서 가장 깊은 왼쪽 노드를 찾는 재귀 함수를 작성하십시오. 가장 깊은 노드를 저장하기 위해 세 개의 인수 루트 노드, isLeftNode 및 결과 포인터가 필요합니다.

• 현재 노드가 왼쪽이고 리프 노드이면 결과 노드를 현재 노드로 업데이트합니다.

• 왼쪽 하위 트리에서 재귀 함수를 호출합니다.

• 오른쪽 하위 트리에서 재귀 함수를 호출합니다.

• 결과 노드가 null이면 조건을 만족하는 노드가 없습니다.

• 그렇지 않으면 결과 노드의 데이터를 인쇄합니다.

예시

코드를 봅시다.

#include <bits/stdc++.h>
using namespace std;
struct Node {
   char data;
   struct Node *left, *right;
};
Node *addNewNode(char data) {
   Node *newNode = new Node;
   newNode->data = data;
   newNode->left = newNode->right = NULL;
   return newNode;
}
void getDeepestLeftLeafNode(Node *root, bool isLeftNode, Node **resultPointer) {
   if (root == NULL) {
      return;
   }
   if (isLeftNode && !root->left && !root->right) {
      *resultPointer = root;
      return;
   }
   getDeepestLeftLeafNode(root->left, true, resultPointer);
   getDeepestLeftLeafNode(root->right, false, resultPointer);
}
int main() {
   Node* root = addNewNode('A');
   root->left = addNewNode('B');
   root->right = addNewNode('C');
   root->left->left = addNewNode('D');
   root->right->left = addNewNode('E');
   root->right->right = addNewNode('F');
   root->right->left->right = addNewNode('G');
   Node *result = NULL;
   getDeepestLeftLeafNode(root, false, &result);
   if (result) {
      cout << "The deepest left child is " << result->data << endl;
   }
   else {
      cout << "There is no left leaf in the given tree" << endl;
   }
   return 0;
}

출력

위의 프로그램을 실행하면 다음과 같은 결과를 얻을 수 있습니다.

The deepest left child is D

결론

튜토리얼에서 질문이 있는 경우 댓글 섹션에 언급하세요.