•
문제 설명 : 0과 1로 구성된 이진트리에서 탐색을 통해 만들 수 있는 이진수의 합을 구하는 문제
•
풀이 방법
◦
DFS를 사용하여, Leef None까지 탐색 후 만들 수 있는 이진수를 stack에 저장한다.
◦
이후 문자열로 구성된 이진수 결과를 합산한다.
•
시간복잡도 :
•
성공 코드
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def sumRootToLeaf(self, root: Optional[TreeNode]) -> int:
stack = []
bits = str(root.val)
self.search_tree(root, bits, stack)
return sum([int(item, 2) for item in stack])
def search_tree(self, node, bits, stack):
if not node.left and not node.right:
stack.append(bits)
return
if node.left != None:
self.search_tree(node.left, bits + str(node.left.val), stack)
if node.right != None:
self.search_tree(node.right, bits + str(node.right.val), stack)
Python
복사