C++で完全二分木の鏡像ノードの合計を中順走査で求める方法

問題概要

この問題では、完全二分木が与えられます。目的は、中順（インオーダー）走査の順序で、完全二分木の鏡像ノードとの合計を求めるプログラムを作成することです。

具体的には、まず左部分木を中順走査し、訪問した各ノードに対して、その鏡像にあたるノードの値を加算していきます。たとえば左側の葉ノードを走査しているときは、対応する右側の葉ノード（鏡像ノード）の値を足すというイメージです。

押さえておきたい基本用語

完全二分木（Complete Binary Tree）

最後のレベルを除くすべてのレベルで、ノード数が最大になっている二分木のことです。

中順走査（Inorder Traversal）

木の走査手法の一つで、「左部分木 → 根 → 右部分木」の順にノードを訪問します。

具体例で理解しよう

入力：

出力： 9 9 17 2

解説： 左部分木を中順走査すると「5 → 7 → 8 → 1」の順に訪問します。

各ノードに鏡像ノードの値を加算すると、次のようになります。

5 + 4 = 9
7 + 2 = 9
8 + 9 = 17
1 + 1 = 2

解き方のアプローチ

この問題を解くには、中順走査を利用して二分木を走査します。ポイントは2つのノードを同時に動かすことです。片方は左部分木を走査するためのもので、もう片方はそのノードの鏡像を訪問するためのものです。

たとえば左部分木の根ノードに対しては、それに対応する鏡像側の根ノード（mirrorroot）を用意し、両者を連動させながら走査を進めます。

C++による実装例

以下は、この解法の動作を示すC++プログラムです。

#include <iostream>
using namespace std;
typedef struct node {
    int data;
    struct node* left;
    struct node* right;
    node(int d){
        data = d;
        left = NULL;
        right = NULL;
    }
} Node;
void printMirrorSum(Node* root, Node* rootMirror){
    if (root->left == NULL && rootMirror->right == NULL)
        return;
    printMirrorSum(root->left, rootMirror->right);
    cout<<(root->left->data + rootMirror->right->data)<<endl;
    printMirrorSum(root->right, rootMirror->left);
}
int main(){
    Node* root = new Node(1);
    root->left = new Node(7);
    root->right = new Node(2);
    root->left->left = new Node(5);
    root->left->right = new Node(8);
    root->right->left = new Node(9);
    root->right->right = new Node(4);
    cout<<"ノードと鏡像ノードの合計："<<endl;
    printMirrorSum(root, root);
    if (root)
        cout<<(root->data + root->data);
    return 0;
}

実行結果

ノードと鏡像ノードの合計：
9
9
17
2