摘要
LeetCode第257题要求生成二叉树的所有从根节点到叶子节点的路径。本文将介绍两种Java解决方案：迭代法和递归法。
1. 问题描述
给定一个二叉树的根节点，按照从根到叶的顺序遍历所有路径，并将它们作为列表的列表返回。
2. 示例分析
输入：[1,2,3,null,null,4]' 输出：[[1,2],[1,3]]`
3. 算法设计
3.1 递归法
递归法的核心思想是深度优先搜索（DFS），从根节点开始，递归遍历左右子树，将当前节点值添加到路径中。
3.2 迭代法
迭代法使用栈来模拟递归的调用栈，同样采用深度优先搜索的思想。
4. Java代码实现
4.1 递归法
public class Solution {
public List<List<Integer>> binaryTreePaths(TreeNode root) {
List<List<Integer>> results = new ArrayList<>();
dfs(root, new ArrayList<>(), results);
return results;
}
private void dfs(TreeNode node, List<Integer> path, List<List<Integer>> results) {
if (node == null) return;
path.add(node.val);
if (node.left == null && node.right == null) {
results.add(new ArrayList<>(path));
}
dfs(node.left, new ArrayList<>(path), results);
dfs(node.right, new ArrayList<>(path), results);
}
}
4.2 迭代法
public class Solution {
public List<String> binaryTreePaths(TreeNode root) {
List<String> results = new ArrayList<>();
if (root == null) return results;
Stack<Pair<TreeNode, String>> stack = new Stack<>();
stack.push(new Pair<>(root, ""));
while (!stack.isEmpty()) {
Pair<TreeNode, String> current = stack.pop();
TreeNode node = current.key;
String path = current.value + (current.value.isEmpty() ? "" : "->") + node.val;
if (node.left == null && node.right == null) {
results.add(path);
} else {
if (node.right != null) {
stack.push(new Pair<>(node.right, path));
}
if (node.left != null) {
stack.push(new Pair<>(node.left, path));
}
}
}
return results;
}
}
5. 代码解析
- 递归法中，
dfs是一个递归辅助方法，用于遍历树并收集路径。 - 迭代法中，使用了一个栈来存储当前节点及其路径，使用
Pair类来存储节点和对应的路径字符串。
6. 测试验证
使用LeetCode平台或其他测试工具对提供的代码进行测试，确保算法的正确性。
7. 总结
LeetCode第257题是一个典型的树遍历问题，可以通过递归或迭代的方式解决。递归法更直观，而迭代法则更节省空间。
8. 参考文献
标签：node,Java,递归,results,二叉树,path,new,null,257 From： https://blog.csdn.net/2301_77695569/article/details/140479173