C++で二分木の後順走査におけるn番目のノードを検索する方法

問題概要

この問題では、二分木と整数Nが与えられます。求められているのは、二分木の後順走査（ポストオーダートラバーサル）におけるN番目のノードを見つけることです。

二分木とは、各ノードが最大2つの子ノードを持つことができる特殊な木構造です。

トラバーサル（走査）とは、木に含まれるすべてのノードを順に訪問する処理のことで、訪問時にノードの値を出力することもあります。

具体例を使って問題を理解しましょう。

入力

N = 6

対象となる二分木は以下の通りです。

        1
       / \
      2   3
     / \ / \
    4  5 6  7

出力

3

説明

この木の後順走査の順序は「4, 5, 2, 6, 7, 3, 1」です。したがって、6番目に訪問されるノードの値は「3」となります。

解決アプローチ

この問題の鍵となるのは、再帰呼び出しを利用した二分木の後順走査です。各再帰呼び出しでは、まず左部分木に対してpostOrder()を呼び出し、続いて右部分木に対してpostOrder()を呼び出し、最後に現在のノード（ルート）を訪問します。

走査の過程では、訪問済みノードの数をカウントしていき、そのカウントがNと一致したノードの値を出力します。

この解決策の動作を示すプログラムは以下の通りです。

実装例

#include <iostream>
using namespace std;

struct Node {
    int data;
    Node* left;
    Node* right;
};

Node* newNode(int val) {
    Node* node = new Node;
    node->data = val;
    node->left = NULL;
    node->right = NULL;
    return node;
}

void postOrder(Node* root, int N, int& counter) {
    if (root == NULL || counter >= N)
        return;
    // 左部分木を走査
    postOrder(root->left, N, counter);
    // 右部分木を走査
    postOrder(root->right, N, counter);
    // 現在のノードを訪問
    counter++;
    if (counter == N)
        cout << N << "番目のノードの値: " << root->data << endl;
}

int main() {
    Node* root = newNode(1);
    root->left = newNode(2);
    root->right = newNode(3);
    root->left->left = newNode(4);
    root->left->right = newNode(5);
    root->right->left = newNode(6);
    root->right->right = newNode(7);

    int N = 6;
    int counter = 0;
    cout << "後順走査: 4 5 2 6 7 3 1" << endl;
    postOrder(root, N, counter);
    return 0;
}

出力

後順走査: 4 5 2 6 7 3 1
6番目のノードの値: 3

計算量の評価

時間計算量：二分木の各ノードを最大1回ずつ訪問するため、O(n) となります。

空間計算量：再帰呼び出しのスタックが木の高さ分必要となるため、最悪の場合（木が大きく偏っている場合）は O(n)、バランスの取れた木であれば O(log n) となります。