二叉树的所有路径

题意

给一棵二叉树,找出从根节点到叶子节点的所有路径。

样例

给出下面这棵二叉树:

   1
 /   \
2     3
 \
  5

所有根到叶子的路径为:

[
  "1->2->5",
  "1->3"
]

思路

如某一个节点,没有子节点则将本身的值加入到集合中,如果有子节点,则将在子节点的路径之前加上当前节点。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
/**
* Definition of TreeNode:
* public class TreeNode {
* public int val;
* public TreeNode left, right;
* public TreeNode(int val) {
* this.val = val;
* this.left = this.right = null;
* }
* }
*/
public class Solution {
/**
* @param root the root of the binary tree
* @return all root-to-leaf paths
*/
public List<String> binaryTreePaths(TreeNode root) {
List<String> paths = new ArrayList<String>();
if (root == null) {
return paths;
}

List<String> leftPaths = binaryTreePaths(root.left);
List<String> rightPaths = binaryTreePaths(root.right);

for (String path : leftPaths) {
paths.add(root.val + "->" + path);
}

for (String path : rightPaths) {
paths.add(root.val + "->" + path);
}

if (paths.size() == 0) {
paths.add(String.valueOf(root.val));
}

return paths;

}
}

原题地址

LintCode:二叉树的所有路径