C++——バランスツリーの判断

12300 ワード
データ構造とアルゴリズム C++
ツリーが与えられ、プログラミングはツリーがツリーであるかどうかを判断します.Leetcode 110問題を例に挙げてみましょう.
へいこうにじゅ
二叉木を与えて、高さバランスのとれた二叉木かどうかを判断します.
この問題では、高さバランスのツリーを次のように定義します.
1つのツリーの各ノードの左右の2つのサブツリーの高さ差の絶対値は1を超えない.
例1:
与えられた二叉木[3,9,20,null,null,15,7]
   3
   / \
  9  20
    /  \
   15   7

trueを返します.
例2:
与えられた二叉木[1,2,2,3,3,null,null,4,4]
      1
      / \
     2   2
    / \
   3   3
  / \
 4   4

falseを返します.
アルゴリズム解析
まず、バランスツリーの判断基準を明らかにします.
3つの要件:1.その左の木はバランスのとれた二叉木です.その右の木はバランスのとれた二叉木です.その左右のサブツリーの高さの差は1以下です
すなわち、左サブツリーまたは右サブツリーがバランスツリーではない場合、または左右のサブツリーの高さ差が1より大きい場合、バランスツリーではありません.
次に,各局所二叉木についてroot,left,right組成と見なすことができ,自然に再帰法を用いることが考えられる.
まずleftサブツリーとrightサブツリーがバランスツリーであるかどうかを判断し,そうでなければfalseに直接戻る.さらに2つの木の高さ差が1以下であるかどうかを判断し,1以上であればfalseに戻る.そうでなければrootをノードとするサブツリーがバランスツリーであることを示し、trueとその高さを返します.
最後に、各層が再帰的に返す値はどれらがありますか?
各層の二叉木について,左右のサブツリーがバランス二叉木(boolタイプ)であるかどうかを知るだけでなく,左右のサブツリーの深さ(intタイプ)も知る必要があり,完全な判断が可能である.ここでは、説明するために新しい構造体を定義することができます.
 struct ReturnNode {
      bool isba;
      int depth;
      ReturnNode(bool i,int d):isba(i),depth(d) {}
  };

最後に、完全なC++コードは以下の通りです.
#include 
#include 
using namespace std;

 struct TreeNode {
      int val;
      TreeNode *left;
      TreeNode *right;
      TreeNode(int x) : val(x), left(NULL), right(NULL) {}
  };

  struct ReturnNode {
      bool isba;
      int depth;
      ReturnNode(bool i,int d):isba(i),depth(d) {}
  };

  ReturnNode* isbalan(TreeNode * root)
  {
      if(root == NULL)
      {
          return new ReturnNode(true,0);
      }

      ReturnNode *r1=isbalan(root->left);
      ReturnNode *r2=isbalan(root->right);
      if(r1->isba == false || r2->isba == false)
      {
          return new ReturnNode(false,0);
      }
      else if(abs(r1->depth-r2->depth)>1)
        return new ReturnNode(false,0);
      else
        return new ReturnNode(true,max(r1->depth,r2->depth)+1);
  }
int main()
{
     TreeNode* root=new TreeNode(3);
     TreeNode* l1=new TreeNode(2);
      TreeNode* r1=new TreeNode(5);
      root->left=l1;
      root->right=r1;
      TreeNode* r2=new TreeNode(7);
      TreeNode* r3=new TreeNode(10);
      l1->right=r2;
      r1->right=r3;

      cout << isbalan(root)->isba << endl;

    return 0;
}

アルゴリズムリファレンス:http://39.96.217.32/blog/4
pythonの閉パッケージと装飾器
プログラミング思想