单位门户网站怎么做seo站长工具平台

思路

这道题目要求从根节点到叶子的路径，所以需要前序遍历，这样才方便让父节点指向孩子节点，找到对应的路径。

在这道题目中将第一次涉及到回溯，因为我们要把路径记录下来，需要回溯来回退一个路径再进入另一个路径。

前序遍历以及回溯的过程如图：

class Solution {public List<String> binaryTreePaths(TreeNode root) {//递归法List<String> res = new ArrayList<>(); //用于存储最终结果集的List，其中每个元素都是一个表示路径的字符串。if(root == null)  return res;List<Integer> paths = new ArrayList<>();//用于在递归过程中构建路径的List，其中每个元素都是二叉树节点的值。traversal(root,paths,res);return res;}//traversal 方法是递归的核心部分，它接受当前节点、路径列表和结果列表作为参数。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();//创建一个StringBuilder对象sb用来拼接字符串，速度更快//遍历路径列表，将paths中的元素按顺序连接成一个路径，并将该路径添加到res集合中。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); //回溯}}
}

注意：

• traversal 方法：

  • traversal 方法是递归的核心部分。它接受当前节点、路径列表和结果列表作为参数。
  • 将当前节点的值添加到路径列表中。
  • 如果当前节点是叶子节点（左右子节点都为空），则执行以下操作：
    • 创建一个 StringBuilder 对象 sb。
    • 通过遍历路径列表，将节点值连接成路径字符串，并使用 -> 分隔。
    • 将路径字符串添加到结果列表中。
  • 无论当前节点是否为叶子节点，都会递归地对左子节点和右子节点执行相同的操作（如果存在的话）。在递归之后，会通过 paths.remove(paths.size() - 1); 进行回溯，移除刚刚添加的节点值，以恢复到上一层的状态。

这行代码 paths.remove(paths.size() - 1);

是在回溯过程中使用的。在递归遍历左子树或右子树之后，程序需要回到当前节点的父节点，继续遍历其他子节点或者回溯到更上层的节点。

因为 paths 列表记录了从根节点到当前节点的路径，当递归返回到父节点时，需要将当前节点从路径中移除，以便继续探索其他分支或者回溯到更上层的节点，保证 paths 列表中记录的是当前路径上的节点序列。这就是为什么在回溯时，需要移除 paths 列表中的最后一个元素的原因。