[LeetCode] Binary Tree Paths 파이썬 (Binary Tree, LCA, DFS)

class Solution(object):
    # @param {TreeNode} root
    # @return {string[]}
    def binaryTreePaths(self, root):
        result, path = [], []
        self.binaryTreePathsRecu(root, path, result)
        return result

    def binaryTreePathsRecu(self, node, path, result):
        if node is None:
            return

        if node.left is node.right is None:
            ans = ""
            for n in path:
                ans += str(n.val) + "->"
            result.append(ans + str(node.val))

        if node.left:
            path.append(node)
            self.binaryTreePathsRecu(node.left, path, result)
            path.pop()

        if node.right:
            path.append(node)
            self.binaryTreePathsRecu(node.right, path, result)
            path.pop()

Binary Tree이기 때문에 left, right 순으로 탐색한다 (DFS)

 

탐색할 때마다 path에 node를 추가

leaf에 도달하는 순간 path에 있는 node.val의 값을 하나씩 꺼내서 string으로 만들고 result에 추가

leaf에서 위로 갈때마다 pop으로 path에 있던 값을 뒤에서부터 하나씩 제거

root 노드의 왼쪽을 다 탐색하고 오른쪽도 탐색하고 나면

종료

 

 

출처: github.com/jiapengwen/LeetCode/blob/master/Python/binary-tree-paths.py