【LeetCode】--- 二叉树的所有路径

用户11288958

发布于 2025-01-24 08:12:04

6200

代码可运行

文章被收录于专栏：学习学习

运行总次数：0

代码可运行

题目传送门

解法一：深度优先搜索（DFS）

算法原理

创建constructPaths方法。传递三个参数TreeNode root, String path, List<String> ret 方法返回值是void 如果当前节点不为null 新建 StringBuffer pathSB 变量将当前节点的值添加到这个变量中，记得要调用一下toString方法Integer.toString(root.val) 接着判断当前节点是否为叶子节点，若是说明当前路径已经探索完毕，将pathSB添加到答案中。若不是，说明当前路径还没有探索完毕，添加 "->" 字符串。接着再去递归左边左边完了再去递归右边

class Solution {
    public List<String> binaryTreePaths(TreeNode root) {
        List<String> ret = new ArrayList<>();
        constructPaths(root, "", ret);
        return ret;
    }

    public void constructPaths(TreeNode root, String path, List<String> ret){
        if(root != null){
            StringBuffer pathSB = new StringBuffer(path);//SB代表当前变量是StringBuffer类型
            //后面需要转成String类型
            pathSB.append(Integer.toString(root.val));
            if(root.left == null && root.right == null){// 当前节点是叶子节点
                ret.add(pathSB.toString());// 把路径加入到答案中
            }else{
                pathSB.append("->");// 当前节点不是叶子节点，继续递归遍历
                constructPaths(root.left,pathSB.toString(),ret);
                constructPaths(root.right,pathSB.toString(),ret);
            }
        }
    }
}