当前位置：首页 > article >正文

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

article 2025/1/31 1:40:59

题目传送门

解法一：深度优先搜索（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);
            }
        }
    }
}