codewars: Fun with trees: is perfect

문제 링크입니다: http://www.codewars.com/kata/fun-with-trees-is-perfect/train/cpp

개인적으로 별로 안 좋아하는 코드입니다.

TreeNode를 구조체로 잡고 이진트리 클래스를 만들었다면 훨씬 간편하고 보기 좋은 코드로 작성할 수 있었겠지만 문제에서 저렇게 정의한 클래스를 가지고 문제를 풀라고 하니 어쩔 수 없었습니다.

/*

2^높이 - 1의 인덱스까지 모두 채워져있는 이진트리를 완전이진트리라고 한다.

isPerfect 함수를 작성하시오

*/

#include <iostream>

#include <queue>

using namespace std;

 

int pow(int height)

{

        int result = 1;

        for (int i = 0; i < height; i++)

               result *= 2;

        return result;

}

 

class TreeNode

{

private:

        TreeNode* left;

        TreeNode* right;

        TreeNode(): left(NULL), right(NULL)

        {

        }

public:

        static bool isPerfect(TreeNode* root)

        {

               // TODO: implementation

               if (root == NULL)

                       return true;

               queue<TreeNode *> q;

               q.push(root);

               int height= getHeight(root), nodeCnt = 1;

               while (1) //노드 갯수를 꾸준히 세는 것이 중요

               {

                       TreeNode *temp = q.front();

                       q.pop();

                       if (temp->left != NULL)

                       {

                              nodeCnt++;

                              q.push(temp->left);

                       }

                       if (temp->right != NULL)

                       {

                              nodeCnt++;

                              q.push(temp->right);

                       }

                       if (q.empty())

                              break;

               }

               if (pow(height) - 1 == nodeCnt) //2^height-1이면 완전이진트리

                       return true;

               else

                       return false;

        }

        static int getHeight(TreeNode *root) //높이 구하는 재귀함수

        {

               if (root == NULL)

                       return 0;

               else

               {

                       int leftHeight = getHeight(root->left);

                       int rightHeight = getHeight(root->right);

 

                       if (leftHeight > rightHeight)

                              return leftHeight + 1;

                       else

                              return rightHeight + 1;

               }

        }

        static TreeNode* leaf() //새로운 노드 생성

        {

               return new TreeNode();

        }

 

        static TreeNode* join(TreeNode* left, TreeNode* right) //새로운 노드 생성하며 왼쪽 오른쪽 모두 추가

        {

               return (new TreeNode())->withChildren(left, right);

        }

 

        TreeNode* withLeft(TreeNode* left) //왼쪽 자식 추가

        {

               this->left = left;

               return this;

        }

 

        TreeNode* withRight(TreeNode* right) //오른쪽 자식 추가

        {

               this->right = right;

               return this;

        }

 

        TreeNode* withChildren(TreeNode* left, TreeNode* right) //양쪽 자식 추가

        {

               this->left = left;

               this->right = right;

               return this;

        }

 

        TreeNode* withLeftLeaf()

        {

               return withLeft(leaf());

        }

 

        TreeNode* withRightLeaf()

        {

               return withRight(leaf());

        }

 

        TreeNode* withLeaves()

        {

               return withChildren(leaf(), leaf());

        }

};

 

int main(void)

{

        TreeNode *root = TreeNode::leaf()->withLeftLeaf(); //LL

        cout << TreeNode::isPerfect(root) << endl;

        root = NULL; //0층

        cout << TreeNode::isPerfect(root) << endl;

        root = TreeNode::leaf()->withLeaves(); //2층 완전 이진 트리

        cout << TreeNode::isPerfect(root) << endl;

        return 0;

}

개발환경:Visual Studio 2017

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~