C++で二分木の最下層・左端の値を求める方法

二分木が与えられたとき、その木の最も深い行（最下層）における左端の値を求める問題を考えてみましょう。例えば、次のような二分木があるとします。

この場合、最下層は [7, 4] であり、その中で最も左にある要素は 7 なので、出力は 7 となります。

解法のアプローチ

この問題は、深さ優先探索（DFS）を利用することでシンプルに解くことができます。ポイントは「必ず左側の子ノードから先に訪問する」ことです。こうすることで、それまでに到達した中で最も深いレベルへ最初に到達したノードが、自動的にそのレベルの左端のノードになります。

アルゴリズムの手順

• 最初に、答えを格納する ans と、現在の最大レベルを記録する lvl という変数を用意します。
• solve() というメソッドを定義します。このメソッドは木のノードとレベルを引数に取り、レベルの初期値は 0 です。動作は以下の通りです。
• ノードが null の場合は何もせずに戻ります。
• level > lvl の場合、ans にノードの値を代入し、lvl を現在のレベルで更新します。
• solve(ノードの左の子, level + 1) を呼び出します。
• solve(ノードの右の子, level + 1) を呼び出します。
• メイン処理では、lvl := -1 と設定し、solve(root) を呼び出した後、ans を返します。

理解を深めるために、以下の実装を見てみましょう。

実装例

#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<auto> v){
    cout << "[";
    for(int i = 0; i<v.size(); i++){
       cout << v[i] << ", ";
    }
    cout << "]"<<endl;
}
class TreeNode{
    public:
    int val;
    TreeNode *left, *right;
    TreeNode(int data){
       val = data;
       left = NULL;
       right = NULL;
    }
};
void insert(TreeNode **root, int val){
    queue<TreeNode*> q;
    q.push(*root);
    while(q.size()){
       TreeNode *temp = q.front();
       q.pop();
       if(!temp->left){
          if(val != NULL)
             temp->left = new TreeNode(val);
          else
             temp->left = new TreeNode(0);
          return;
       } else {
          q.push(temp->left);
       }
       if(!temp->right){
          if(val != NULL)
             temp->right = new TreeNode(val);
          else
             temp->right = new TreeNode(0);
          return;
       } else {
          q.push(temp->right);
       }
    }
}
TreeNode *make_tree(vector<int> v){
    TreeNode *root = new TreeNode(v[0]);
    for(int i = 1; i<v.size(); i++){
       insert(&root, v[i]);
    }
    return root;
}
class Solution {
    public:
    int ans;
    int lvl;
    void solve(TreeNode* node, int level = 0){
       if(!node || node->val == 0) return;
       if(level > lvl){
          ans = node->val;
          lvl = level;
       }
       solve(node->left, level + 1);
       solve(node->right, level + 1);
    }
    int findBottomLeftValue(TreeNode* root) {
       lvl = -1;
       solve(root);
       return ans;
    }
};
main(){
    vector<int> v = {3,5,1,6,2,0,8,NULL,NULL,7,4};
    TreeNode *tree = make_tree(v);
    Solution ob;
    cout <<(ob.findBottomLeftValue(tree));
}

入力

[3,5,1,6,2,0,8,null,null,7,4]

出力

7

計算量について

このアルゴリズムでは、各ノードを一度だけ訪問するため、時間計算量は O(n)（n はノード数）となります。また、再帰の深さは木の高さに依存するため、空間計算量は O(h)（h は木の高さ）です。最悪の場合、木が線形に偏っていると O(n) になりますが、バランスの取れた木であれば O(log n) に抑えられます。