C++의 이진 트리 기울기

이진 트리의 루트 노드가 있다고 가정해 보겠습니다. 작업은 모든 노드의 기울기의 합을 찾아 반환하는 것입니다.

기울기 이진 트리의 구성은 각 수준에서 왼쪽 하위 트리와 오른쪽 하위 트리에서 자식 노드의 절대 차이를 찾아 이진 트리를 구성하는 것뿐입니다. 특정 수준에서 자식 노드가 없는 노드는 해당 노드를 0으로 교체하여 간단히 기울입니다.

예

입력

<강한>

출력: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입니다.

이 문제를 해결하기 위한 접근 방식

이 특정 문제를 해결하는 간단한 방법은 Post Order Breadth First Search 순회를 사용하는 것입니다.

이진 트리를 탐색하는 동안 왼쪽 하위 트리와 오른쪽 하위 트리의 모든 노드의 합을 찾으려고 시도합니다. 합을 찾으면 하위 트리의 왼쪽 합계와 오른쪽 합계의 절대 차이를 계산하여 모든 노드의 기울기를 찾습니다.

• 입력이 될 이진 트리를 가져옵니다.
• 정수 함수 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입니다.