크래프톤 정글 WEEK5 Day37 - Binary Tree

📆2024.2.13

 

오늘 Binary Tree 과제 다 풀었다......

모든 문제가 재귀로 푸는 형식이라 접근방식은 다 비슷해서 금방 풀 수 있었다.

그리고 어제 스택 풀면서 봤던 괄호 문제 찾아서 백준 괄호 문제 풀고, 프로그래머스 코딩 기초 트레이닝 캘린더 도장 깨기 하고 있다. 내일은 BST 다 풀고 책 ,키워드 공부해야겠다!

 

 

 

Binary Tree

identical

 

두 개의 이진 트리가 구조적으로 동일한지 판별

int identical(BTNode *tree1, BTNode *tree2)
{
   /* add your code here */
    if(tree1 == NULL && tree2 == NULL)          //두 트리가 모드 비어있으면 동일하다고 판단
        return 1;
    else if(tree1 != NULL && tree2 != NULL){
        return(
            tree1->item == tree2->item &&      
            identical(tree1->left, tree2->left) &&
            identical(tree1->right,tree2->right)  
        );
    }
    else
        return 0;
}

 

maxHeight

 

재귀 이용해서 최대 높이 나타냄

int maxHeight(BTNode *node)
{
    /* add your code here */ 
    if(node == NULL)    return -1;
    else
    {
        int l = maxHeight(node->left);   
        int r = maxHeight(node->right);

        if(l > r)   return l + 1;
        else    return r + 1;
    }
}

 

countOneChildNodes

 

재귀를 이용해서 홀수인 노드의 합을 구해라

int sumOfOddNodes(BTNode *node)
{
    /* add your code here */
    if(node == NULL) return 0;
    else if(node->item % 2 == 1)
    {
        return sumOfOddNodes(node->left) + sumOfOddNodes(node->right) + node->item;
    }
    else    
        return sumOfOddNodes(node->left) + sumOfOddNodes(node->right);
}

 

 

mirrorTree

 

void mirrorTree(BTNode *node)
{
	/* add your code here */
    if(node == NULL)    return;
    else
    {
        //현재 노드의 왼쪽 서브트리와 오른쪽 서브트리 스왑
        BTNode *temp;
        temp = node->left;
        node->left = node->right;
        node->right = temp;

        mirrorTree(node->left);
        mirrorTree(node->right);
    }

}

 

printSmallerValues

 

void printSmallerValues(BTNode *node, int m)
{
	/* add your code here */
    if(node == NULL)    return;
    else
    {
        if(node->item < m)
        {
            printf("%d ", node->item);
        }
        //왼쪽 오른쪽 서브트리 모두 탐색
        printSmallerValues(node->left, m);      
        printSmallerValues(node->right,m);
    }
}

 

smallestValue

 

int smallestValue(BTNode *node)
{
	/* add your code here */
    if(node == NULL)   return -1;
    else if(node->left == NULL && node->right == NULL)
        return node->item;
    else
    {
        int leftsmall = smallestValue(node->left);
        int rightsmall = smallestValue(node->right);

        if(leftsmall > rightsmall) 
            return rightsmall;
        else
            return leftsmall;
    }
}

 

hasGreatGrandchild

 

int hasGreatGrandchild(BTNode *node)
{
	/* add your code here */
    if(node == NULL) return -1;
    else
    {
        int l = hasGreatGrandchild(node->left);
        int r = hasGreatGrandchild(node->right);   

        if(l + 1 > 2 || r + 1 > 2)          
            printf("%d ", node->item);
        return ((l > r) ? l : r ) + 1;
    }
}