C++の二分木で最も深い左葉ノード

このチュートリアルでは、二分木で最も深い左葉ノードを見つけます。二分木を見てみましょう。

   A
      B    C
D       E       F
                     G

問題を解決するための手順を見てみましょう。

• char、left、rightポインタを使用してNode構造体を記述します。

• ダミーデータで二分木を初期化します。

• 再帰関数を記述して、バイナリ関数の左端のノードを見つけます。最も深いノードを格納するには、3つの引数のルートノード、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

結論

チュートリアルに質問がある場合は、コメントセクションにそのことを記載してください。