C++での二分木傾斜

二分木のルートノードがあるとしましょう。タスクは、すべてのノードの傾きの合計を見つけて返すことです。

傾斜 バイナリツリーの例は、各レベルの左側のサブツリーと右側のサブツリーの子ノードの絶対差を見つけることによってバイナリツリーを構築することに他なりません。ある特定のレベル、つまり子ノードを持たないノードでは、そのノードをゼロに置き換えるだけで傾斜します。

例

入力

出力：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

この問題を解決するためのアプローチ

この特定の問題を解決するための簡単なアプローチは、注文後の幅優先探索トラバーサルを使用することです。

二分木をトラバースしている間、左側のサブツリー、次に右側のサブツリーのすべてのノードの合計を見つけようとします。合計が見つかったら、サブツリーの左の合計と右の合計の絶対差を計算することにより、すべてのノードの傾きを見つけます。

• 入力となる二分木を取ります。
• 整数関数sumNodes（treenode * node）は、ツリーのルートノードを取得し、左側のサブツリーと右側のサブツリーの合計を返します。
• 整数関数findTilt（treenode * root）は、ルートノードを入力パラメーターとして受け取り、すべてのノードの傾きの合計を返します。

例

#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 &amp; 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です。