博客

二叉树的所有路径

概述：给你一个二叉树的根节点


root


，按任意顺序，返回所有从根节点到叶子节点的路径。叶子节点是指没有子节点的节点。

输入：root = [1,2,3,null,5]
输出：["1->2->5","1->3"]

输入：root = [1]
输出：["1"]

方法一：深度优先搜索

思路：思路比较直观，首先找到根节点，然后判断孩子节点是不是叶子节点，依次循环即可。

# 深度优先搜索
# 思路比较直观，首先找到根节点，然后判断孩子节点是不是叶子节点，依次循环即可。
class Solution:
    def binaryTreePaths(self, root: Optional[TreeNode]) -> List[str]:
        def construct_paths(root, path):
            if root:
                path += str(root.val)
                if not root.left and not root.right:
                    paths.append(path)
                else:
                    path += '->'
                    construct_paths(root.left, path)
                    construct_paths(root.right, path)
        paths = []
        construct_paths(root, '')
        return paths

方法二：广度优先搜索

思路：核心思路不变，不同在于建立一个队列来存储，依次循环输出即可。

# 广度优先搜索
# 核心思路不变，不同在于建立一个队列来存储，依次循环输出即可。
class Solution:
    def binaryTreePaths(self, root: TreeNode) -> List[str]:
        paths = list()
        if not root:
            return paths

        node_queue = collections.deque([root])
        path_queue = collections.deque([str(root.val)])

        while node_queue:
            node = node_queue.popleft()
            path = path_queue.popleft()

            if not node.left and not node.right:
                paths.append(path)
            else:
                if node.left:
                    node_queue.append(node.left)
                    path_queue.append(path + '->' + str(node.left.val))
                
                if node.right:
                    node_queue.append(node.right)
                    path_queue.append(path + '->' + str(node.right.val))
        return paths

总结

最近是回溯月吗。。。