최대 굽힘 수가 있는 C++ 경로 길이

이진 트리가 주어진 문제를 해결하기 위해. 이제 최대 굽힘 수가 있는 경로를 찾아야 합니다. 즉, 경로의 방향이 왼쪽에서 오른쪽으로 또는 그 반대로 변경될 때 굽힘으로 간주됩니다. 예를 들어

입력 -

출력 -

6

이제 이 접근 방식에서 우리는 트리를 가로질러 이전 움직임을 추적할 것입니다. 방향이 변경되면 단순히 굽힘 수를 업데이트한 다음 최대값을 찾습니다.

해결책을 찾기 위한 접근 방식

이 접근 방식에서 우리는 모든 경로를 횡단하고 답을 업데이트하는 최대 굽힘 수를 찾습니다.

예시

#include <bits/stdc++.h>
using namespace std;
struct Node { // structure of our node
    int key;
    struct Node* left;
    struct Node* right;
};
struct Node* newNode(int key){ // initializing our node
    struct Node* node = new Node();
    node->left = NULL;
    node->right = NULL;
    node->key = key;
    return node;
}
void maximumBends(struct Node* node,char direction, int bends,
                    int* maxBends, int soFar,int* len){
    if (node == NULL) // if null is reached
       return;
    if (node->left == NULL && node->right == NULL) { // if we reach the leaf node then
                                                   //we check if we have to update our answer or not
        if (bends > *maxBends) {
            *maxBends = bends;
            *len = soFar;
        }
    }
    else {
        if (direction == 'l') { // current direction is left
            maximumBends(node->left, direction,bends, maxBends,soFar + 1, len);
            maximumBends(node->right, 'r',bends + 1, maxBends,soFar + 1, len); // if we change direction so bend also increases
        }
        else {
            maximumBends(node->right, direction,bends, maxBends,soFar + 1, len);
            maximumBends(node->left, 'l',bends + 1, maxBends,soFar + 1, len); // same as when direction was left
        }
    }
}
int main(){
    struct Node* root = newNode(10);
    root->left = newNode(8);
    root->right = newNode(2);
    root->left->left = newNode(3);
    root->left->right = newNode(5);
    root->right->left = newNode(2);
    root->right->left->right = newNode(1);
    root->right->left->right->left = newNode(9);
    int len = 0, bends = 0, maxBends = -1;
    if(!root) // if tree is empty
       cout << "0\n";
    else{
        if (root->left) // if left subtree exists
            maximumBends(root->left, 'l',bends, &maxBends, 1, &len);
        if (root->right) // if right subtree exists
            maximumBends(root->right, 'r', bends,&maxBends, 1, &len);
        cout << len << "\n";
    }
    return 0;
}

출력

4

위 코드 설명

위의 접근 방식에서 우리는 단순히 모든 경로를 횡단하고 경로의 끝에 도달했을 때 지금까지 발견된 굽힘을 계산합니다. 즉, 리프 노드입니다. 여기까지의 굽힘이 이전 최대값보다 큰지 확인합니다. 조건이 참이므로 최대 굽힘과 이 새 길이에 대한 경로의 길이를 업데이트하고 이것이 프로그램이 진행되는 방식입니다.

결론

이 자습서에서는 최대 굽힘 수가 있는 경로 길이를 찾는 문제를 해결합니다. 우리는 또한 이 문제에 대한 C++ 프로그램과 이 문제를 해결하는 완전한 접근 방식(Normal)을 배웠습니다. C, Java, python 및 기타 언어와 같은 다른 언어로 동일한 프로그램을 작성할 수 있습니다. 이 튜토리얼이 도움이 되기를 바랍니다.