LeetCode 257. 二叉树的所有路径
原题链接
简单
作者:
caichuntao
,
2023-06-25 16:58:06
,
所有人可见
,
阅读 81
方法1:DFS
时间复杂度:$O(n^2)$
空间复杂度:最坏$O(n^2)$
解题思路
https://leetcode.cn/problems/binary-tree-paths/solution/er-cha-shu-de-suo-you-lu-jing-by-leetcode-solution/
Java 代码
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public List<String> binaryTreePaths(TreeNode root) {
List<String> paths = new ArrayList<>();
addPath(root, "", paths);
return paths;
}
public void addPath(TreeNode root, String path, List<String> paths) {
if (root == null) return;
StringBuilder sb = new StringBuilder(path);
sb.append(Integer.toString(root.val));
if (root.left == null && root.right == null) {
paths.add(sb.toString());
} else {
sb.append("->");
addPath(root.left, sb.toString(), paths);
addPath(root.right, sb.toString(), paths);
}
}
}