인프런 커뮤니티 질문&답변

작성한 질문수

자바(Java) 알고리즘 문제풀이 입문: 코딩테스트 대비

9. Tree 말단노드까지의 까장 짧은 경로(DFS)

if 조건식에서 불완전트리일 경우에 대한 처리

작성

262

자식이 하나밖에 없는 불완전 트리일 경우 재귀로 반환된 자기 자신이 root인지 검사하면 되는 것 아닐까요?

아래 소스처럼 수정해도 정답이 나오는 것 같습니다.

반례가 떠오르지 않는데.. 혹시 있을까요?

```

if (root == null || (root.lt == null && root.rt == null)) {
    return L;
} else {
...
}

```

퀴즈

66%나 틀려요. 한번 도전해보세요!

재귀 함수가 자신을 호출할 때, 매개변수, 지역 변수, 복귀 주소 등이 저장되는 메모리 영역의 구조는 무엇일까요?

힙 영역 (Heap area)

스택 프레임 (Stack Frame)

큐 (Queue)

데이터 세그먼트 (Data Segment)

답변 2

지식공유자

안녕하세요^^

네. 그럴것 같네요.

혹시 소스코드 수정하면 아래와 같은 경우에는 3이 아니라 2가 나오지 않을까요?

저는 그냥 1. 리프노드일 경우 2. 자식이 양쪽 모두 있을 경우 3.자식이 왼쪽에만 있을 경우 4. 자식이 오른쪽에만 있을 경우 로 일일이 나눠서 풀었습니다.

만약에 문제에 트리 높이 제한이 서술되어 있다면 root == null 일때 (최대 트리 높이 + 1) 나 (최대 트리 높이)를 리턴하면 깔끔해질 수도 있을 것 같습니다.

작성한 질문수