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

この記事では、二分木（バイナリツリー）が与えられたときに、その中から最も深いノードを見つける問題について解説します。

二分木と最も深いノードとは

二分木はデータの格納に用いられる特別なデータ構造で、「各ノードが持てる子ノードは最大2つまで」という条件を満たすのが特徴です。

二分木における最も深いノードとは、木の中で最大の高さ（深さ）に位置するノードのことを指します。

具体例で理解しよう

入力：

出力： 8

この例では、ノード8が最も深い位置にあるため、答えは8となります。

解法アプローチ

この問題には複数の解き方がありますが、基本となる考え方は共通しています。「木の高さを求め、その高さにあるノードまで走査して結果を返す」というものです。以下に、有望かつ効率的な解法を2つ紹介します。

解法1：レベルを追跡しながら走査する

シンプルな解法の一つは、木を中順走査（inorder traversal）でたどりながら現在のレベルを記録し、現在のレベルがmaxLevelを超えたときにそのノードをdeepestNodeとして更新していく方法です。すべてのノードの走査が完了した時点で、deepestNodeを返します。木の走査には再帰を利用します。

この解法の時間計算量はO(n)、空間計算量は木の高さhに対してO(h)となります。

ソリューションの動作を示すプログラム：

#include <iostream>
using namespace std;
struct Node{
    int data;
    struct Node *left, *right;
};
Node *newNode(int data){
    Node *temp = new Node;
    temp->data = data;
    temp->left = temp->right = NULL;
    return temp;
}
void findDeepestNodeRec(Node *root, int currentLevel, int &maxLevel, int &deepestNode){
   if (root != NULL){
      findDeepestNodeRec(root->left, ++currentLevel, maxLevel, deepestNode);
      if (currentLevel > maxLevel){
         deepestNode = root->data;
         maxLevel = currentLevel;
      }
      findDeepestNodeRec(root->right, currentLevel, maxLevel, deepestNode);
   }
}
int findDeepestNodeBT(Node *root){
   int deepestNode = 0;
   int maxLevel = 0;
   findDeepestNodeRec(root, 0, maxLevel, deepestNode);
   return deepestNode;
}
int main(){
   Node* root = newNode(3);
   root->left = newNode(5);
   root->right = newNode(4);
   root->left->left = newNode(1);
   root->left->right = newNode(9);
   root->right->left = newNode(6);
   root->right->left->right = newNode(8);
   cout<<"指定された二分木の最も深いノードは "<<findDeepestNodeBT(root);
   return 0;
}

出力

指定された二分木の最も深いノードは 8

解法2：木の高さを先に計算する

もう一つのアプローチは、まず与えられた木の高さを計算し、その高さと同じレベルに位置するノードを出力する方法です。

ソリューションの動作を示すプログラム：

#include <bits/stdc++.h>
using namespace std;
struct Node{
    int data; struct Node *left, *right;
};
Node *newNode(int data){
    Node *temp = new Node;
    temp->data = data;
    temp->left = temp->right = NULL;
    return temp;
}
int calcHeight(Node* root){
    if(!root) return 0;
    int leftHt = calcHeight(root->left) + 1;
    int rightHt = calcHeight(root->right) + 1;
    return max(leftHt, rightHt);
}
void findDeepestNodeBT(Node* root, int levels){
    if(!root) return;
    if(levels == 1)
    cout << root->data;
    else if(levels > 1){
       findDeepestNodeBT(root->left, levels - 1);
       findDeepestNodeBT(root->right, levels - 1);
    }
}
int main(){
    Node* root = newNode(3);
    root->left = newNode(5);
    root->right = newNode(4);
    root->left->left = newNode(1);
    root->left->right = newNode(9);
    root->right->left = newNode(6);
    root->right->left->right = newNode(8);
    int maxHeight = calcHeight(root);
    cout<<"二分木の最も深いノードは ";
   findDeepestNodeBT(root, maxHeight);
    return 0;
}

出力

二分木の最も深いノードは 8

まとめ

どちらの解法も木全体を一度だけ走査するため、時間計算量はO(n)です。レベルを追跡する方法は1回の走査で完結できる一方、高さを先に計算する方法は処理の流れが明確で理解しやすいという利点があります。目的や可読性の要件に応じて使い分けるとよいでしょう。