"이진 트리가 주어지면 모든 루트에서 리프 경로를 반환"이라는 코딩 문제를 해결하려고합니다.
Input:
1
/ \
2 3
\
5
Output: ["1->2->5", "1->3"]
나는 하나의 해결책을 보았다
class Solution:
def binaryTreePaths(self, root: TreeNode) -> List[str]:
allPath = []
if root is None:
return []
self.find_all_paths_recursive(root, [], allPath)
return allPath
def find_all_paths_recursive(self, currNode, currPath, allPath):
if currNode is None:
return
currPath.append(currNode.val)
if currNode.left is None and currNode.right is None:
currOut = '->'.join([str(x) for x in list(currPath)])
allPath.append(currOut)
# traverse left sub tree
self.find_all_paths_recursive(currNode.left, currPath, allPath)
# traverse right sub tree
self.find_all_paths_recursive(currNode.right, currPath, allPath)
del currPath[-1]
위의 코드를 실행하면 [ "1-> 2-> 5", "1-> 3"]의 답이 나왔는데 맞습니다.
나는 아래의 코드 블록을 변경하여 생각 if currNode.left is None and currNode.right is None:에
if currNode.left is None and currNode.right is None:
#currOut = '->'.join([str(x) for x in list(currPath)])
#allPath.append(currOut)
allPath.append(currPath)
결과 [[1,2,5], [1,3]]를 줘야합니다. 그러나이 변경으로 결과 [[], []]가 반환되었습니다. 왜 이것이 작동하지 않는지 궁금합니다.
currPath를 직접 추가하려면 해당 순간에 currPath의 사본을 추가해야합니다.
이렇게 :
if currNode.left is None and currNode.right is None:
#currOut = '->'.join([str(x) for x in list(currPath)])
# allPath.append(currOut)
allPath.append(list(currPath))
편집하다:
추가하지 않으면 list재귀로 인해 업데이트되는 allPath에 원래 목록 개체가 추가됩니다. 를 추가하면 lista를합니다 copy of the original list object저장 및 추가 업데이트하지 될합니다.
이 기사는 인터넷에서 수집됩니다. 재 인쇄 할 때 출처를 알려주십시오.
침해가 발생한 경우 연락 주시기 바랍니다[email protected] 삭제
몇 마디 만하겠습니다