C++で二分木の傾斜（Tilt）を求めるアルゴリズムと実装方法

二分木の傾斜とは？

二分木の根ノードが与えられたとき、すべてのノードの傾斜（tilt）の合計を求めて返すことを考えます。

二分木の傾斜とは、木の各ノードについて「左部分木に含まれるノード値の合計」と「右部分木に含まれるノード値の合計」の絶対差を計算して得られる値です。子ノードを持たないノード（葉ノード）については、左右どちらの部分木も存在しないため、その傾斜は0として扱います。

具体例

入力：

出力：15

与えられた二分木の各ノードにおける傾斜を求めると、以下のようになります。

• ノード3の傾斜 = 0（葉ノードのため）
• ノード5の傾斜 = 0（葉ノードのため）
• ノード7の傾斜 = 0（葉ノードのため）
• ノード2の傾斜 = abs(3 − 5) = 2
• ノード9の傾斜 = abs(0 − 7) = 7
• ノード4の傾斜 = abs((3 + 5 + 2) − (9 + 7)) = 6

すべてのノードの傾斜の合計 = 2 + 7 + 6 = 15

問題を解くためのアプローチ

この問題を解く最もシンプルな方法は、後順走査（Post-order Traversal）を利用することです。後順走査では「左の子 → 右の子 → 自身」の順でノードを訪問するため、あるノードの傾斜を計算する時点で、その左右の部分木の合計値がすでに求まっているという利点があります。

二分木を走査しながら、まず左部分木の全ノードの合計値を求め、次に右部分木の合計値を求めます。両者の合計が得られたら、その絶対差を計算することで現在のノードの傾斜がわかります。これを再帰的に繰り返し、全体の傾斜の合計を累積していきます。

アルゴリズムの手順

• 入力として二分木を受け取ります。
• 整数型関数 sumNodes(treenode* node) は、木の根ノードを受け取り、左部分木と右部分木のノード値の合計を返すとともに、参照渡しの変数 sum に各ノードの傾斜を加算していきます。
• 整数型関数 findTilt(treenode* root) は、根ノードを入力パラメータとして受け取り、すべてのノードの傾斜の合計を返します。

C++での実装例

#include<iostream>
using namespace std;
struct treenode {
    int data;
    treenode * left;
    treenode * right;
};
struct treenode * createNode(int d) {
    struct treenode * root = new treenode;
    root -> data = d;
    root -> left = NULL;
    root -> right = NULL;
    return root;
}
int sumNodes(treenode * root, int & sum) {
    if (root == NULL) return 0;
    int lsum = sumNodes(root -> left, sum);
    int rsum = sumNodes(root -> right, sum);
    sum += abs(lsum - rsum);
    return lsum + rsum + root -> data;
}
int findTilt(treenode * root) {
    int sum = 0;
    if (root == NULL) {
        return 0;
    }
    sumNodes(root, sum);
    return sum;
}
int main() {
    struct treenode * root = NULL;
    root = createNode(4);
    root -> left = createNode(2);
    root -> right = createNode(9);
    root -> left -> right = createNode(5);
    root -> left -> left = createNode(3);
    root -> right -> right = createNode(7);
    cout << findTilt(root) << endl;
    return 0;
}

上記のコードを実行すると、次の出力が得られます。

出力結果

15

まとめ

この二分木において、すべてのレベルの全ノードの傾斜の合計は15となります。このアルゴリズムの計算量は、各ノードを一度だけ訪問するため O(N)（Nはノード数）、必要なメモリは再帰呼び出しのスタック深さに依存し、平衡な木の場合は O(log N)、最悪ケース（線形リスト状の木）では O(N) となります。