【Leetcode Daily】257二叉树的所有路径

题目浅析

• 想查看原题可以点击题目链接。

• 简单地说，就是给一个二叉树，要求根到每个叶子节点的路径。

思路分享

• 灵神给出了递归和回溯两种思路。前者让路径通过参数传递，每个节点只要在前面的基础加上自己的值，然后遍历下一层前补上路径衔接（这是题目要求的 ->）；后者则在外面维护答案，python 中可以通过 join 函数把列表连成字符串，不过就相当于在递归之间维护一个栈，进入点就压栈，退出点就弹栈。

  https://leetcode.cn/problems/binary-tree-paths/solutions/3038189/liang-chong-xie-fa-lu-jing-wei-can-shu-h-q2wz/

代码解答（强烈建议自行解答后再看）

• 参考题解

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def binaryTreePaths(self, root: Optional[TreeNode]) -> List[str]:
        ans = []
        cur = []
        def dfs(root:Optional[TreeNode]):
            if not root:
                return 
            nonlocal cur 
            cur.append(str(root.val))
            # print(root.val, cur)
            if not root.left and not root.right:
                nonlocal ans 
                ans.append("->".join(cur))
            else:
                dfs(root.left)
                dfs(root.right)
            cur.pop()
            # print(root.val, cur)
        dfs(root)
        return ans