완전 이진트리 판별 어캐하냐??

[륄슨(platinum456)]

내가 생각해서 짠 게 아니네ㅠㅠ

[ㄴㅇㄹ(124.197)]

Recursion으로 해결한다

[ㄴㅇㄹ(124.197)]

isComplete(node) 함수 :

[ㄴㅇㄹ(124.197)]

1. 내가 child가 없다면 -> return true

[ㄴㅇㄹ(124.197)]

2. 왼쪽자식만 있거나 오른쪽 자식만 있다면 -> return false

[ㄴㅇㄹ(124.197)]

3. 두 자식 모두 있다면 -> return isComplete(node->left) and isComplete(node->right)

[0xrgb(0xrgb)]

위의 풀이 반례있다

[ㄴㅇㄹ(124.197)]

어떤 경우에??

[ㄴㅇㄹ(124.197)]

아 알았다 높이도 같이 반환해야하는구나

[ㄴㅇㄹ(124.197)]

isComplete(node) 함수를 int로 반환하도록 해서

[ㄴㅇㄹ(124.197)]

내가 child가 없다면 -> return 1

[ㄴㅇㄹ(124.197)]

왼쪽 자식만 있거나 오른쪽 자식만 있다면 -> return -1

[ㄴㅇㄹ(124.197)]

두 자식이 모두 있다면 -> isComplete(node->left), isComplete(node->right)가 -1이 아니고 일치하는 경우엔 return isComplete(node->left)+1, 그렇지 않을땐 -1

[륄슨(platinum456)]

감사합니다