Python이 "2차 트리의 모든 경로"를 구현하는 두 가지 방법

1658 단어 Algorithms
두 갈래 나무를 정해서 뿌리 결점에서 잎 결점까지의 모든 경로를 되돌려준다
참고:
잎사귀 결점에 자목이 없다
Example:
Input:

   1
 /   \
2     3
 \
  5

Output: ["1->2->5", "1->3"]

Explanation: All root-to-leaf paths are: 1->2->5, 1->3

1: 귀속

def binaryTreePaths(self, root):
        """
        :type root: TreeNode
        :rtype: List[str]
        """
        if not root:
            return []
        if not root.left and not root.right:
            return [str(root.val)]
        pathList = []
        if root.left:
            pathList += self.binaryTreePaths(root.left)
        if root.right:
            pathList += self.binaryTreePaths(root.right)
        for index, path in enumerate(pathList):
            pathList[index] = str(root.val) + "->" +path
        return pathList

2: 교체(타인 참조)

def binaryTreePaths(self, root):
        """
        :type root: TreeNode
        :rtype: List[str]
        """
        if not root:
            return []
        pathList, stack = [], [(root, "")]
        while stack:
            node, pathStr = stack.pop(0)
            if not node.left and not node.right:
                pathList.append(pathStr + str(node.val))
            if node.left:
                stack.append((node.left, pathStr + str(node.val) + "->"))
            if node.right:
                stack.append((node.right, pathStr + str(node.val) + "->"))
        return pathList

알고리즘 문제:https://leetcode-cn.com/problems/valid-anagram/description/

좋은 웹페이지 즐겨찾기