Home Forums US Life tree 의 높이 구하는 알고리듬…이해가… tree 의 높이 구하는 알고리듬…이해가… Name * Password * Email "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 } ` I agree to the terms of service Comment
