C++で二分木の最も深い左葉ノードを見つける方法

このチュートリアルでは、C++を使って二分木の中から最も深い位置にある左葉ノード（deepest left leaf node）を見つける方法を解説します。まず、対象となる二分木の構造を確認しましょう。

   A
  B    C
D    E    F
           G

この木の場合、左側の子として接続されている葉ノードは「D」だけなので、答えは D となります。それでは、問題を解くための手順を順番に見ていきましょう。

解決手順

• char型のデータと左右の子ポインタを持つ Node 構造体を定義します。
• ダミーデータを使って二分木を初期化します。
• 最も深い左葉ノードを探索する再帰関数を作成します。この関数は「現在のノード」「そのノードが左の子かどうかを示すフラグ」「結果を格納するポインタ」の3つの引数を受け取ります。
• 現在のノードが左の子であり、かつ葉ノード（子を持たないノード）であれば、結果ポインタを現在のノードで更新します。
• 左部分木に対して再帰関数を呼び出します。
• 右部分木に対しても再帰関数を呼び出します。
• 探索後、結果ノードが NULL の場合は条件を満たすノードが存在しないことを意味します。
• 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

処理のポイント

このアルゴリズムの鍵となるのは、再帰呼び出しの際に渡す isLeftNode フラグです。左の子へ潜るときは true を、右の子へ潜るときは false を渡すことで、「そのノードが親から見て左側の子であるか」を正確に追跡できます。さらに、左右どちらの子も持たないノードだけを候補とすることで、葉ノードであることも同時に判定しています。

計算量は木の全ノードを一度ずつ訪問するため、ノード数を n とすると O(n)、空間計算量は再帰の深さに依存し、最悪ケースで O(n) となります。

まとめ

今回は、C++における再帰的な木の走査を利用して、二分木の最も深い左葉ノードを見つける方法を学びました。このテクニックは、木構造に関するさまざまな応用問題にも役立ちます。チュートリアルについて質問がある場合は、コメント欄でお気軽にお尋ねください。