最大ベンド数の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 ++プログラムと、この問題を解決するための完全なアプローチ（通常）についても学びました。同じプログラムを、C、java、python、その他の言語などの他の言語で作成できます。このチュートリアルがお役に立てば幸いです。