力扣257. 二叉树的所有路径（递归回溯与迭代）

题目：

给你一个二叉树的根节点?root?，按?任意顺序?，返回所有从根节点到叶子节点的路径。

叶子节点?是指没有子节点的节点。

示例 1：

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

示例 2：

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

提示：

• 树中节点的数目在范围?[1, 100]?内
• -100 <= Node.val <= 100

思路：?

这道题目要求从根节点到叶子的路径，所以需要前序遍历（中左右），这样才方便让父节点指向孩子节点，找到对应的路径。

先用递归的方法来做，走过的路径用path来表示，每遍历一个节点就加入到path中，递归遍历节点

递归完，要做回溯，因为path 不能一直加入节点，它还要删节点，然后才能加入新的节点。此时就需要用到回溯来删走过的节点，回溯和递归是一一对应的，有一个递归，就要有一个回溯。

代码及思路：

递归回溯：

# 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]:
        # 定义一个列表来存储路径
        path = []
        # 定义一个列表来存储结果
        result = []
        # 如果根节点为空，直接返回结果列表
        if not root:
            return result
        # 进行前序遍历
        self.traversal(root, path, result)
        return result
        
    def traversal(self, node, path, result):
        # 将当前节点的值加入路径中   
        path.append(node.val)
        # 如果当前节点是叶子节点，将路径转化为字符串并加入结果列表中  （中）
        if not node.left and not node.right:
            spath = '->'.join(map(str, path))
            result.append(spath)
            return
        # 如果有左子节点，进行递归遍历，并将左子节点从路径中弹出  （左）
        if node.left:
            self.traversal(node.left, path, result)
            path.pop()   # 回溯
        # 如果有右子节点，进行递归遍历，并将右子节点从路径中弹出  （右）
        if node.right:   
            self.traversal(node.right, path, result)
            path.pop()   # 回溯

迭代法：

# 定义二叉树节点的类
# 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]:
        # 使用栈来存储节点
        stack = [(root)]
        # 使用栈来存储路径
        path_st = [str(root.val)]
        result = []
        while stack:
            # 弹出节点
            node = stack.pop()
            # 弹出路径
            path = path_st.pop()
            # 如果节点没有左右子节点，说明到达叶子节点，将路径加入结果中
            if not node.left and not node.right:
                result.append(path)
            # 如果有右子节点，将右子节点和路径加入栈中
            if node.right:
                stack.append(node.right)
                path_st.append(path + '->' + str(node.right.val))
            # 如果有左子节点，将左子节点和路径加入栈中
            if node.left:
                stack.append(node.left)
                path_st.append(path + '->' + str(node.left.val))
        return result