Leetcode 257-二叉树的所有路径

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

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

题解

递归+回溯
遇到叶节点返回
每层的做法,list加上当前节点的string值

本题解将res作为全局变量，作为局部变量写法也是一样的
dfs的参数怎么确定？ 需要进入下一层的参数（树节点/链表节点、中间结果集、最终结果集）
dfs怎么回溯？ 进入某个分支的遍历后弹出当前路径的最后一个节点
dfs怎么返回？ 遇到满足条件的结果集后将其加入最终结果集

代码最后暗含回溯
遍历完左子树，构建出合格的路径，加入解集，遍历右子树之前，路径要撤销最末尾的选择，如果path用的是数组，就会弹出最后一项。
这里用的字符串，保存了当前节点的路径，s+=root.val+"->"会创建一个新的字符串。递归右子树时，传入它即可，因为它不包含在递归左子树所拼接的东西

class Solution {
    //递归+回溯
    //遇到叶节点返回
    //每层的做法,list加上当前节点的string值


    //本题解将res作为全局变量，作为局部变量写法也是一样的
    //dfs的参数怎么确定？需要进入下一层的参数（树节点/链表节点、中间结果集、最终结果集）
    //dfs怎么回溯？进入某个分支的遍历后弹出当前路径的最后一个节点
    //dfs怎么返回？遇到满足条件的结果集后将其加入最终结果集
    List<String> res = new ArrayList<>();
    public List<String> binaryTreePaths(TreeNode root) {
        //List<String> res = new ArrayList<>();
        String s="";
        dfs(root,s);
        return res;
    }

   //递归终止条件：
    public void dfs(TreeNode root,String s) {
        //边界条件
        if(root==null){
            return;
        }
        
        //递归终止条件：当前节点为叶节点
        if(root.left==null&&root.right==null){
            s+=root.val;
            res.add(s);//遇到叶节点后将当前路径加入结果集
        }
        
        //不是叶节点，则需要+"->"并继续向下递归
        s+=root.val+"->";
/*此处暗含回溯
遍历完左子树，构建出合格的路径，加入解集，遍历右子树之前，路径要撤销最末尾的选择，如果path用的是数组，就会弹出最后一项。
这里用的字符串，保存了当前节点的路径，s+=root.val+"->"会创建一个新的字符串。递归右子树时，传入它即可，因为它不包含在递归左子树所拼接的东西。
*/
        dfs(root.left,s);
        dfs(root.right,s);
    }
    
}