C++でツリーの高さがバランスされているかどうかを確認するプログラム

二分木があるとしましょう。高さがバランスしているかどうかを確認する必要があります。高さのバランスが取れたツリーの場合、ツリー内のすべてのノードについて、左側のサブツリーの高さと右側のサブツリーの高さの絶対差は0または1であることがわかっています。

したがって、入力が次のような場合

その場合、出力はTrueになります

これを解決するには、次の手順に従います-

• 関数dfs（）を定義します。これはノードを取ります

• ノードがnullの場合、-

  • 0を返す

• l：=1 + dfs（ノードの左側）

• r：=1 + dfs（ノードの右側）

• | l--r|の場合> 1、次に-

  • ret：=false

• lとrの最大値を返す

• メインの方法から、次のようにします-

• ret：=true

• dfs（root）

• retを返す

理解を深めるために、次の実装を見てみましょう-

例

#include <bits/stdc++.h>
using namespace std;
class TreeNode {
   public:
   int val;
   TreeNode *left;
   TreeNode *right;
   TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
class Solution {
   public:
   bool ret;
   int dfs(TreeNode* node){
      if(!node)
         return 0;
      int l = 1 + dfs(node->left);
      int r = 1 + dfs(node->right);
      if(abs(l - r) > 1)
         ret = false;
      return max(l, r);
   }
   bool isBalanced(TreeNode* root) {
      ret = true;
      dfs(root);
      return ret;
   }
};
main(){
   Solution ob;
   TreeNode *root = new TreeNode(25);
   root->left = new TreeNode(19);
   root->right = new TreeNode(4);
   root->left->left = new TreeNode(9);
   root->left->right = new TreeNode(7);
   cout << (ob.isBalanced(root));
}

入力

TreeNode *root = new TreeNode(25);
root->left = new TreeNode(19);
root->right = new TreeNode(4);
root->left->left = new TreeNode(9);
root->left->right = new TreeNode(7);

出力

1