[좌충우돌, 파이썬으로 자료구조 구현하기] 형제 노드가 없는 노드 찾기

문제

이진트리가 있을 때, 형제 노드가 없는 노드의 키를 출력하라. 형제 노드가 없는 노드가 없으면 -1을 출력하라.

      37
     /
   20
  /
113

출력: [20, 113]

풀이

형제 노드를 찾으려면 레벨 순서 순회를 해야한다.

레벨 순서 순회를 하면서 left 노드가 있을 때, right 노드가 없으면 결과 리스트에 해당 노드를 추가해준다.

반대의 경우도 마찬가지이다.

def find_has_no_sibling(tree):
    res, q = [], [tree.root]

    while q:
        node = q.pop(0)
        if node.left:
            q.append(node.left)
            if not node.right:
                res.append(node.left.data)
                continue
        if node.right:
            q.append(node.right)
            if not node.left:
                res.append(node.right.data)
                continue
    return res if res else [-1]

실행 결과

tree1 = Tree()
tree1.make_tree([37, 20, None, 113])
print(find_has_no_sibling(tree1))

>>> [20, 113]

tree2 = Tree()
tree2.make_tree([1,2,3])
print(find_has_no_sibling(tree2))

>>> [-1]

tree3 = Tree()
tree3.make_tree(["A", "B", "C", "D", "E", "F", None, "G"])
print(find_has_no_sibling(tree3))

>>> ['F', 'G']