Leetcode 257-二叉树的所有路径

本文主要是介绍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);}}