알고리즘 분석 - 트리

이진트리에서 왼쪽 서브트리의 노드 개수가 오른쪽 서브트리의 노드 개수보다 작은 노드의 개수 구하기

이진트리에서 노드 i의 왼쪽 서브트리의 노드 개수를 Left(i)라 하고 오른쪽 서브트리의 노드 개수를 Right(i)라 할 때,

Left(i) < Right(i)인 노드 i의 개수를 구하는 알고리즘을 재귀법(recursion)을 사용해서 작성하기

 

#include <iostream>
#include <fstream>
#include <string>
using namespace std;

int tree[1001][2] = {-1, };
int ans = 0;
int l = 0; int r = 0;

int height(int root) {
    if(root == -1) return 0;
    int hLeft = height(tree[root][0]);
    int hRight = height(tree[root][1]);
    return (hLeft > hRight) ? hLeft + 1 : hRight + 1;
}

void preorder(int root) { 
    if(root == -1) return;
    int lH;
    int rH;
    lH = height(tree[root][0]);
    rH = height(tree[root][1]);
    if(lH < rH) ans++; // 오른쪽 subtree node 개수가 더 많을 때
    
    preorder(tree[root][0]); // lc
    preorder(tree[root][1]); // rc
}

int main() {
    ifstream ifile;
      
    ifile.open("input.txt");

    if(ifile.is_open()) {
//       while(!ifile.eof()) {
            int t;
            ifile >> t; // testcase 개수
            for (int i = 0; i < t; i++) {
                int N; // 1 <= N <= 1000
                ifile >> N;
                for (int j = 0; j < N; j++) {
                    int root, lc, rc;
                    ifile >> root >> lc >> rc;
                    tree[root][0] = lc;
                    tree[root][1] = rc;
                }
                preorder(1);
                cout << ans;
                cout << '\n';
                ans = 0;
                /*트리 초기화*/
                for (int i = 0; i < 1001; i++) {
                    for (int j = 0; j < 2; j++) {
                        tree[i][j] = -1;
                    }
                }
            }
  //      }
    }
    ifile.close(); // 파일 닫기

    return 0;
}