根到叶路径问题：遍历框架 + 前中后序位置 + 路径记录 + 叶子节点处理

根到叶路径问题

257. 二叉树的所有路径
129. 求根节点到叶节点数字之和
112. 路径总和
113. 路径总和 II
437. 路径总和 III
988. 从叶结点开始的最小字符串
124. 二叉树中的最大路径和

257. 二叉树的所有路径

问题描述：找出所有从根节点到叶子节点的路径，并以字符串形式返回每条路径。

题目链接：https://leetcode.cn/problems/binary-tree-paths/

解题思路：

遍历二叉树：遍历整棵树以访问每个节点。这是解决问题的基础，确保每个节点都被检查以构造路径。
记录路径：在遍历过程中，需要记录从根节点到当前节点的路径。

通过一个列表或字符串来实现，每访问一个节点，就将该节点的值添加到路径中。
识别叶子节点：叶子节点是没有子节点的节点。

当遇到叶子节点时，意味着找到了一条完整的路径，因为路径是从根节点到叶子节点的。
保存路径：一旦到达叶子节点，就将当前记录的路径保存下来。

将路径添加到一个结果列表中，因为题目要求列出所有这样的路径。
回溯：在遍历二叉树时，每当从一个节点返回到它的父节点时，需要从当前路径中移除这个节点。

当探索完一个节点的所有子节点后，我们需要回溯以探索同一父节点的其他子节点（如果有的话），这时当前节点不应该出现在新的路径中。

整个逻辑链条是：DFS允许我们从根节点开始，深入每个分支，直到到达叶子节点，然后保存路径，并回溯删除已添加的结果路径，探索其他分支。

DFS 代码框架：

void dfs(TreeNode root) {      # 遍历二叉树
    if (root == null) return;  # 最基础的情况
    dfs(root.left);            # 进入左子树
    dfs(root.right);           # 进入右子树   
}

前中后序位置：

void dfs(TreeNode root) {
    if (root == null) return; 
    //【前序位置】: 进入节点前做
    dfs(root.left);       
    //【中序位置】: 左子树都遍历完，即将开始遍历右子树的时候执行
    dfs(root.right);      
    //【后序位置】: 离开右节点（收集完该节点所有子树的信息）后做，在回溯到其父节点之前执行的（返回到它的父节点继续之前的遍历过程，继续执行父节点处的递归调用的下一步）
}

在这里插入图片描述

对于这题：

如果单独抽出一个二叉树节点，它需要做什么事情？
需要在什么时候（前/中/后序位置）做？

节点需要做的事情?

记录路径：每个节点在路径中的位置需要被记录下来。
判断是否为叶子节点：如果一个节点是叶子节点（即没有左右子节点），那么它就代表一条完整的路径的终点。

这时，我们需要把当前构建的路径保存起来，因为这条路径是完整的，从根节点到叶子节点的路径。
路径回溯：在完成对当前节点及其子树的遍历后，我们需要回溯。也就是说，在返回到父节点之前，当前节点应该从路径中移除，以便正确地构建其他的路径。

在什么时候做?

记录路径（前序位置）：在遍历到一个节点之前，我们应该把这个节点加入到当前路径中。这是因为无论这个节点最后是否成为一条完整路径的一部分，我们都需要先记录下它的值。这个操作适合在前序位置做，即在递归地探索左右子节点之前。
判断是否为叶子节点（前序位置）
路径回溯（后序位置）：在完成了当前节点的所有子节点的遍历后（找到了一条路径），即在递归函数返回到父节点之前，我们应该从路径中移除当前节点。

在添加完一条路径后，我们需要回溯，以便探索树中的其他路径。

这意味着，当递归调用完成并且准备返回其父节点时，我们从path中移除当前节点。

这一步是关键的，它恢复了path到父节点状态，从而为探索父节点的其他子节点（例如从左子树转向右子树）准备好了环境。

当我们从path中移除一个节点，实际上是在进行路径的回溯，而不是直接移除一条完整路径。

这个回溯（撤销之前的选择）步骤确保了每当我们回到一个分支点（如一个有两个子节点的父节点），path都能正确地反映出当前探索的路径。

回溯，就是回退一步。

完整代码：

class Solution:
    def binaryTreePaths(self, root: Optional[TreeNode]) -> List[str]:
        # 初始化遍历，启动深度优先搜索
        self.traverse(root)
        return self.res

    path = []  # 用于暂存当前路径的节点值
    res = []  # 存储所有从根到叶的路径

    def traverse(self, root: Optional[TreeNode]) -> None:
        if not root:  # 基底情况：节点为空，直接返回
            return
        
        # 叶子节点判断：左右子节点均为空
        if not root.left and not root.right:
            self.path.append(str(root.val))  # 添加当前节点值到路径
            self.res.append("->".join(self.path))  # 路径转换为字符串并存储
            self.path.pop()  # 回溯，从路径中移除当前叶子节点
            return
        
        self.path.append(str(root.val))  # 做选择，添加当前节点值到路径（前序遍历操作）
       
        self.traverse(root.left)
        self.traverse(root.right)
        
        self.path.pop()  # 撤销选择（回溯），从路径中移除当前节点（后序遍历操作）

129. 求根节点到叶节点数字之和

问题描述：计算从根节点到叶子节点生成的所有数字之和。这里每条路径代表一个数字，由该路径上的节点值依次连接而成。

题目链接：https://leetcode.cn/problems/sum-root-to-leaf-numbers/description/

257题解法：通过深度优先搜索遍历树，记录遍历过程中从根到当前节点的路径。遇到叶子节点时，将这条路径作为一个字符串添加到结果列表中。

129题解法：同样使用深度优先搜索遍历树，但是在遍历过程中，将从根到当前节点形成的数字累加起来。遇到叶子节点时，将累加得到的数字加到总和中。

这题比上一题多了一个特征：数字的累加。

class Solution:
    def sumNumbers(self, root: Optional[TreeNode]) -> int:
        self.totalSum = 0
        self.numberPath = []  # 用于模拟构建路径数字的过程
        self.traverse(root)
        return self.totalSum

    def traverse(self, root: Optional[TreeNode]) -> None:
        if not root:
            return
        
        # 添加当前节点值到路径数字中（模拟数字的构建）
        self.numberPath.append(root.val)
        
        # 如果是叶子节点，计算当前路径数字并累加到总和中
        if not root.left and not root.right:
            self.totalSum += int(''.join(map(str, self.numberPath)))
        
        self.traverse(root.left)
        self.traverse(root.right)
        
        # 撤销选择（回溯）：移除路径数字的最后一个元素（模拟撤销数字的最后一位）
        self.numberPath.pop()