Leetcode 257. 二叉树的所有路径

力扣传送门(opens new window)

给定一个二叉树，返回所有从根节点到叶子节点的路径。

说明: 叶子节点是指没有子节点的节点。

示例 1：

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

示例 2：

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

解题思路

思路解析：
要求返回二叉树中所有从根节点到叶子节点的路径，可以使用深度优先搜索（DFS）的方法来解决。具体思路如下：

1. 定义一个辅助函数 dfs，该函数用于进行深度优先搜索，并将路径保存在一个列表中。
2. 在 dfs 函数中，首先进行一个判断，如果当前节点为空，即到达了叶子节点的空子节点，那么将当前路径加入结果列表中。
3. 如果当前节点不为空，那么将当前节点的值加入到路径中，并递归调用 dfs 函数，分别处理左子树和右子树。
4. 在递归调用之后，需要将路径中的当前节点值删除，以便处理其他路径。
5. 编写主函数 binaryTreePaths，用于调用 dfs 函数并返回结果列表。
6. 在主函数中，首先进行一个判断，如果根节点为空，即整棵树为空树，那么返回一个空的结果列表。
7. 如果根节点不为空，那么创建一个空的结果列表，然后调用 dfs 函数，将结果存储在列表中。
8. 返回结果列表作为最终的答案。

通过深度优先搜索，可以遍历二叉树中的所有路径，并将满足条件的路径保存在结果列表中，最终返回结果列表作为答案。

代码实现：

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public List<String> binaryTreePaths(TreeNode root) {
        // 存储结果的列表
        List<String> paths = new ArrayList<>(); 
        // 如果根节点为空，返回空的结果列表
        if (root == null) {
            return paths;
        }
        // 调用深度优先搜索函数
        dfs(root, "", paths); 
        return paths;
    }

    private void dfs(TreeNode node, String path, List<String> paths) {
        // 到达叶子节点时，将当前路径加入结果列表
        if (node.left == null && node.right == null) {
            // 将当前节点值加入路径
            path += node.val; 
             // 将路径加入结果列表
            paths.add(path);
            return;
        }
        // 将当前节点值加入路径，并添加箭头符号
        path += node.val + "->"; 
        // 递归处理左子树
        if (node.left != null) {
            dfs(node.left, path, paths); 
        }
         // 递归处理右子树
        if (node.right != null) {
            dfs(node.right, path, paths);
        }
    }
}