Skip to content

257. Binary Tree Paths

难度: 简单

刷题内容

原题连接

  • https://leetcode.com/problems/binary-tree-paths

内容描述

Given a binary tree, return all root-to-leaf paths.

Note: A leaf is a node with no children.

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

递归+DFS

class Solution(object):
    def binaryTreePaths(self, root):
        """
        :type root: TreeNode
        :rtype: List[str]
        """
        def helper(node, cur_path):
            if not node.left and not node.right: ## 到leaf了
                res.append(cur_path+[node.val])
                return
            if node.left:
                helper(node.left, cur_path+[node.val])
            if node.right:
                helper(node.right, cur_path+[node.val])

        res = []  
        if not root:
            return res
        helper(root, [])

        return ['->'.join([str(val) for val in path]) for path in res]

注意一点,很多人可能看到这里有好几次cur_path+[node.val],觉得干嘛不直接写在最开头了,事实是这样做的话cur_path就已经变化了,因为要执行完if node.left才去执行if node.right,此时cur_path就不是原来的cur_path了。



回到顶部