二分木で最も深い左葉（左の葉ノード）を見つけるC++プログラム

二分木とは、各ノードが最大2つの子ノード（左の子と右の子）を持つ木構造のことです。本記事では、二分木の中から最も深い位置にある左葉（親ノードから見て左側の子である葉ノード）を見つけるC++プログラムを紹介します。

アルゴリズム

開始。
    関数 deepestLLeafutil() は、与えられた二分木の中から
    最も深い左葉を探索します。
        lvel   ：現在のノードのレベル（深さ）
        maxlvel：これまでに見つかった最も深い左葉のレベルへのポインタ
        isLeft ：このノードが親の左の子であることを示すフラグ
        resPtr ：結果ノードへのポインタ
        もし root が NULL ならば、
            return する。
        このノードが左葉であり、かつそのレベルが現在の
        結果の最大レベルよりも大きい場合は、結果を更新する。
        左右の部分木に対して関数 deepestLLeafutil() を再帰的に呼び出す。
終了。

プログラムの考え方

このアルゴリズムでは、深さ優先探索（DFS）を用いて木全体を走査します。各ノードに到達した際に、以下の条件をすべて満たしていれば、そのノードを候補として記録します。

• 親ノードの左の子である（isLeft が true）
• 左右どちらの子も持たない葉ノードである
• これまでに見つかった左葉よりも深いレベルにある

条件を満たすノードが見つかるたびに、結果ポインタと最大レベルを更新していくことで、走査の終了時には最も深い左葉が得られます。計算量はノード数を n とすると O(n) であり、各ノードを一度だけ訪問するため効率的です。

サンプルコード

#include <iostream>
using namespace std;
struct n {
    int v;
    n *l, *r;
};
void deepestLLeafutil(n *root, int lvel, int *maxvel, bool isLeft, n **resPtr) {
    if (root == NULL)
        return;
    if (isLeft && !root->l && !root->r && lvel > *maxvel) {
        *resPtr = root;
        *maxvel = lvel;
        return;
    }
    deepestLLeafutil(root->l, lvel + 1, maxvel, true, resPtr);
    deepestLLeafutil(root->r, lvel + 1, maxvel, false, resPtr);
}
n* deepestLLeaf( n *root) {
    int maxlevel = 0;
    n *res = NULL;
    deepestLLeafutil(root, 0, &maxlevel, false, &res);
    return res;
}
n *newnode(int d) {
    n *t = new n;
    t->v = d;
    t->l = t->r = NULL;
    return t;
}
int main() {
    n* root = newnode(9);
    root->l = newnode(7);
    root->r = newnode(10);
    root->l->l = newnode(6);
    root->r->l= newnode(8);
    root->r->r = newnode(19);
    root->r->l->r = newnode(4);
    root->r->r->r = newnode(20);
    n *res = deepestLLeaf(root);
    if (res)
        cout << "The deepest left leaf is " << res->v;
    else
        cout << "There is no left leaf in the given tree";
    return 0;
}

サンプルツリーの構造

上記のコードで構築される二分木は次のような構造になっています。

              9
           /     \
          7       10
         /       /  \
        6       8    19
                 \     \
                  4     20

この木において、左葉となるのは 6 のみです。ノード 8 の右の子である 4 は右側の子なので左葉には該当せず、したがって最も深い左葉は 6 となります。

出力

The deepest left leaf is 6

まとめ

本プログラムでは、DFSによる再帰的な走査と「左の子かつ葉ノード」という条件判定を組み合わせることで、二分木内の最も深い左葉を効率よく特定できます。左葉が存在しない木の場合は、その旨を通知する処理も含まれており、実用的な実装となっています。