“2. 리커시브 방식을 쓰지 못하게 하고 BFS 로 접근하게(또는 하나의 아이터레이터 루프로만) 구현하고 싶다면 리커시브보다 상당히 복잡해질거 같은 생각이 드네요”
음 BFS로 해도 별로 어렵지 않습니다. parent에서 child로 넘어갈때 자신이 가지고 있는 height + 1을 넘겨주면 되지요. 그럼 Leaf 노드 까지 진행시 height가 증가하게 되고, 그 중에서 가장 큰 값이 Tree height가 되는 것이죠.
from collections import deque # double ended queue
def tree_height(root) {
q = deque([(root, 1)]) # (node, height) as tuple
treeHeight = 0
while len(q) > 0:
node, height = q.pop(0) # pop the first item
treeHeight = max(treeHeight , height) # update the treeHeight
if node.left:
q.append((node.left, height+1))
if node.right:
q.append((node.right, height+1))
return treeHeight
}