前言
算法的重要性不言而喻！区分度高！
现在学习的门槛低了，只有能上网每个人都可以学编程！培训班6个月就可以培养出来能干活的人，你怎么从这些人中脱颖而出？没错！就是学算法，学一些底层和基础的东西。
说的功利点是为了竞争，卷死对手。真心话说就是能提高自己的基础能力，为技术可持续发展做好充分的准备！！！
提前入门学习书籍：CPrimerPlus、大话数据结构
刷题网站
我是按照代码随想录提供的刷题顺序进行刷题的，大家也可以去刷leetcode最热200道，都可以
刷题嘛，最重要的就是坚持了！！！
画图软件
OneNote
这个要经常用，遇见不懂的流程的话就拿它画一画！
笔记软件
Typoral
题目
解析
确定思路
题目要求的是根节点到叶子结点的路径，所以要从根节点开始，那么我们就需要用前序遍历。
除了确认前序遍历，我们今天还要新了解一个概念；那就是回溯！什么是回溯呢？由于是第一次出现这个词语我们没必要深究。举个例子给大家理解：
- 就比如这道题，找到父节点到叶子结点的路径之后，还需要清空这个顺序
- 清空顺序这个过程其实就是回溯的过程
ok，就了解这么多后面我们有专门的专题去练习回溯。
计算路径
下面的这个路径该怎么表示呢?
["1->2->5","1->3"]
很明显它是一个字符串集合,字符是节点的数值加上一个"->"标识
那我们不是只要把节点的值取出来然后再加上这个->标识不就行了吗?
对,没错! 但是有一个注意点,如果我们把每个节点的值拿出来之后加上这个->标识,那这个字符串整体不就变成了1->2->5->这样了吗?我们想要的是1->2->5这样的啊喂!
怎么解决呢?
我们可以先不把最后一个元素加入这个字符串中,等待倒数第二个加完我们就结束,最后一个字符我们手动添加不就行了?
就是这个意思:当我们添加到1->2->这样之后就停止添加;最后我们在添加最后一个节点的元素值.这样就可以实现1->2->5这样的效果了!
具体代码如下:
//把每个节点的值添加进字符串中 paths.add(root.val); //递归到了叶子结点,开始计算路径 if(root.left == null && root.right == null){ StringBuilder sb = new StringBuilder(); //i< paths.size() - 1这里不遍历到最后一个元素，是因为“->”的原因 //最后一个元素我们手动加入 for(int i = 0;i< paths.size() - 1;i++){ sb.append(paths.get(i)).append("->"); } sb.append(paths.get(paths.size() -1)); res.add(sb.toString()); return; }
回溯的过程
第一条路径搞好了,我们还要添加第二条路径呢,但是paths这个集合里,存放的都是第一条路径的节点值,所以我们需要把它们给全部取出来!这就是回溯的过程!
可以发现,递归往往都是和回溯相伴!
递归是直接干到最后一个节点,然后慢慢往上走.
回溯自然也是从最后一个节点,然后慢慢踢出节点的值
if(root.left != null){ traversal(root.left,paths,res); paths.remove(paths.size() - 1);//回溯的过程 } if(root.right != null){ traversal(root.right,paths,res); paths.remove(paths.size() -1 );//回溯 }
完整代码如下
class Solution { public List<String> binaryTreePaths(TreeNode root) { //存放的路径结果集 List<String> res = new ArrayList<>(); //边界条件判断 if(root == null){ return res; } //存放节点的值 List<Integer> paths = new ArrayList<>(); traversal(root,paths,res); return res; } //计算二叉树的所有路径，并回溯 private void traversal(TreeNode root,List<Integer> paths, List<String> res){ paths.add(root.val); //递归到了叶子结点,开始计算路径 if(root.left == null && root.right == null){ StringBuilder sb = new StringBuilder(); //i< paths.size() - 1这里不遍历到最后一个元素，是因为“->”的原因 //最后一个元素我们手动加入 for(int i = 0;i< paths.size() - 1;i++){ sb.append(paths.get(i)).append("->"); } sb.append(paths.get(paths.size() -1)); res.add(sb.toString()); return; } if(root.left != null){ traversal(root.left,paths,res); paths.remove(paths.size() - 1);//回溯的过程 } if(root.right != null){ traversal(root.right,paths,res); paths.remove(paths.size() -1 );//回溯 } } }
测试
