C++の連続ツリー

連続ツリーは、ルートノードからリーフノードへのパスがノードの値または重みを持ち、親ノードとそのすべての直接子ノードの絶対差が常に1になるツリーとして定義されます。

ルートからリーフへのパス上のノードを選択すると、

|ノードの重み-左の子ノードの重み|=|左の子ノードの重み-ノードの重み| =1、これは正しい子にも当てはまります

|ノードの重み-右の子ノードの重み|=|右の子ノードの重みl-ノードの重み| =1

図

例を挙げて理解しましょう。

下のツリーは、親ノードとその子の絶対差が常に1であるため、連続しています。

以下のツリーは、連続ツリーとしての資格がありません。

ツリーが連続しているかどうかを調べるアルゴリズム

• ルートがNULLの場合、1を返します

• リーフノードの場合は、ツリーが連続しているため1を返します。これが、リーフノードに到達した理由です。

• 左側のサブツリーが空の場合は、現在のノードと右側の子の連続性を確認し（重みの絶対差を計算）、右側のサブツリーを再帰的に続行します。

• 右側のサブツリーが空の場合は、現在のノードと左側の子の連続性を確認し（重みの絶対差を計算）、左側のサブツリーを再帰的に続行します。

• それ以外の場合は、左右の子の重みとの絶対差を計算し、再帰的に左右のサブツリーを続行します。

擬似コード

// Function to check tree is continuous or not
struct btreeNode{
   int data;
   btreeNode* left, * right;
};
int isContinuous(btreeNode *root){
   // if node is NULL return 1, exit condition
   if (root == NULL)
      return 1;
   //if leaf node is reached then tree must be continous during this path
   if (root->left == NULL && root->right == NULL)
      return 1;
   // if no left child
   if (root->left == NULL)
      return (abs(root->data - root->right->data) == 1) && isContinuous(root->right);
   // if no right child
   if (root->right == NULL)
      return (abs(root->data - root->left->data) == 1) && isContinuous(root->left);
      // calculate absoute difference
      return abs(root->data - root->left->data)==1 && abs(root->data - root->right->data)==1 &&
   isContinuous(root->left) && isContinuous(root->right);
}