目录

• 前言
• • 题目
  • 1.递归和回溯
  • 2. 本题思路分析：
  • 3. 算法实现
  • 4. pop函数的算法复杂度
  • 5. 算法坑点

前言

在本科毕设结束后，我开始刷卡哥的“代码随想录”，每天一节。自己的总结笔记均会放在“算法刷题-代码随想录”该专栏下。
代码随想录此题链接

题目

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

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

1.递归和回溯

1. 遍历所有的路径，从头到尾，所以肯定是前序遍历，使用递归
2. 并且需要遍历所有路径，必然是遇到叶子节点要往上回退，需要使用到回溯

2. 本题思路分析：

1. 递归三部曲，第一步确定参数和返回值。

• 参数应该是，当前节点，当前走过节点的列表，以及组成的字符串类型的列表

2. 第二步确定递归截止条件，当遇到叶子节点，停止递归。

• 叶子节点既是左右孩子均为空的节点，此时生成这条路的路径

3. 第三步，单层递归逻辑

• 因为是前序遍历，所以在截止条件前就必须先处理中间节点，既是将中间节点加入到路径数组中（paths中），
• 截止条件判断
• 之后就是处理左右孩子，判断左右孩子是否为空，不为空则递归，并且递归结束还需要回溯，删除路径数组中最后一个元素。

3. 算法实现

• 代码：
  //递归法（后序遍历）因为是求高度，所以是后序遍历

class Solution {
//整体是前序遍历
public List binaryTreePaths(TreeNode root) {List result = new ArrayList();List paths = new ArrayList();getPath(paths,result,root);return result;
}public void getPath(List paths,List pathStrs,TreeNode root){//需要加入当前节点  前序中首先是“中”，之后才是“左”、“右” paths.add(root.val);if(root.left == null && root.right == null){//终止条件:遇到叶子节点//则将遇到的所有paths转换成strStringBuilder path = new StringBuilder("");for(int i = 0;i < paths.size() - 1;i++){path.append(paths.get(i)).append("->");}pathStrs.add(path.append(paths.get(paths.size() - 1)).toString());}//???单层递归循环if(root.left != null){getPath(paths,pathStrs,root.left);paths.remove(paths.size() - 1);//ArrayList删除的API,删除指定下标的元素}if(root.right != null){getPath(paths,pathStrs,root.right);paths.remove(paths.size() - 1);}}
}

4. pop函数的算法复杂度

暂无

5. 算法坑点

暂无