C++의 연속 트리

연속 트리는 루트 노드에서 리프 노드까지의 모든 경로가 상위 노드와 모든 직계 자식 노드 간의 절대 차이가 항상 1이 되도록 노드의 값 또는 가중치를 갖는 트리로 정의됩니다.

루트에서 리프까지의 경로에서 노드를 선택하면

|노드의 가중치-왼쪽 자식 노드의 가중치|=|왼쪽 자식 노드의 가중치-노드의 가중치| =1, 이것은 오른쪽 자식에게도 적용됩니다.

|노드의 가중치-오른쪽 자식 노드의 가중치|=|오른쪽 자식 노드의 가중치 lo-노드의 가중치| =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);
}