dcddc

西米大人的博客

0%

二叉树的所有路径

发表于 更新于 分类于 热度: ℃ 评论: ℃
字数： 159 阅读时长 ≈ 1 分钟
lintcode题目

题目描述

给一棵二叉树，找出从根节点到叶子节点的所有路径。
例子：给出下面这棵二叉树：

1
2
3
4
5
   1
 /   \
2     3
 \
  5

所有根到叶子的路径为：
[
“1->2->5”,
“1->3”
]

思路

递归。
如果当前节点存在左右子树，优先递归左子树，再递归右子树。
如果当前节点不存在子树，将当前节点添加到String后，将String加入到list

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
private List<String> strings;
    public List<String> binaryTreePaths(TreeNode root) {
        // Write your code here
        strings = new ArrayList<>();
        String str = "";
        findLeaf(root, str);
        return strings;
    }
    
    private void findLeaf(TreeNode root, String str) {
        if(root == null) {
            return;
        }
        String  str1 = root.val + "->";
        str = str + str1;
        if(root.left == null && root.right == null) {
            strings.add(str.substring(0, str.length()-2));
            return;
        }else {
            findLeaf(root.left, str);
            findLeaf(root.right, str);
        }
    }

考差点