LC257. 二叉树的所有路径

  • Post author:
  • Post category:其他


隐含回溯,先序遍历类似

class Solution(object):
    def binaryTreePaths(self, root):
        """
        :type root: TreeNode
        :rtype: List[str]
        """
        res,sol = [],""
        def backtrack(root,sol):
            if root:
                sol += str(root.val)
                if not root.left and not root.right:
                    res.append(sol[:])
                    return
                else:
                    sol += "->"
                    backtrack(root.left,sol)
                    backtrack(root.right,sol)
                    return
        backtrack(root,sol)
        return res

标准回溯

def binaryTreePaths(self, root):
    """
    :type root: TreeNode
    :rtype: List[str]
    """
    res = []
    path = []
    def backTracking(root):
        path.append(root.val)
        if not root.left and not root.right:
            res.append('->'.join(str(item) for item in path))
            return
        if root.left:
            backTracking(root.left)
            path.pop()
        if root.right:
            backTracking(root.right)
            path.pop()
    backTracking(root)
    return res



版权声明:本文为weixin_44392348原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。