수다닷컴

질문 제목 : 이진 트리 equal 함수 구현 약간의 힌트 부탁드립니다.이진 트리 equal 함수 구현질문 내용 :

자료구조 책을 보다가 equal 구현이 나왔는데
같은 트리구조인지, 각각의 노드가 정확히 일치하는지를 판단해야하거든요.

일단 노드 개수가 다르면 다른 트리일거고, 최대 레벨이 다르면 다른 트리일거라는 것은 알겠고요.

위 두 개의 조건을 통과했다고 해도 같은 구조가 아닌 트리의 생김새는 이것 저것 떠오르네요.
(노드의 개수가 같고 최대레벨이 같더라도 다른 구조가 나올 수 있지요.)

다 제쳐두고 노드 개수랑 최대 레벨이 같으면 같은 구조를 가졌다고 생각하고
순회 하면서 노드를 비교하더라도 일단 노드 개수를 세거나 최대 레벨(height)을 판단하거나 할 때도
순회를 하게 될텐데 이러면 너무 효율이 안좋은거 아닌가 싶어서요,,

잘 짜여진 알고리즘이라든가 보고 싶은데 검색해도 찾을 수가 없네요.
코드를 짜달라고 말씀드리는게 아니라 해당 알고리즘이 짜여있는 곳의 링크가 있으면 혹시 첨부를 부탁드릴 수 있으신가 하는 것이고요.
꼭 그런게 아니라도 어떤 어떤 과정을 거쳐서 하면 되겠구나 하는 힌트 좀 주실 수 있을까 해서 올려봅니다.

신청하기