257. 二叉树的所有路径

原题链接：

257. 二叉树的所有路径

https://leetcode.cn/problems/binary-tree-paths/description/

完成情况：

解题思路：

用dfs去遍历，找路径，一直追加，到了叶子结点就输出出去。
1

参考代码：

_257二叉树的所有路径_找路径一般都是dfs

package 代码随想录.树.二叉树;

import 代码随想录.树.TreeNode;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

public class _257二叉树的所有路径_找路径一般都是dfs {
    /**
     *返回所有从根节点到叶子节点的路径。
     *
     * @param root
     * @return
     */
    public List<String> binaryTreePaths(TreeNode root) {
        List<String> listPaths = new ArrayList<String>();
        constructPath(root, "", listPaths);
        return listPaths;
    }

    /**
     *
     * @param root
     * @param path
     * @param listPaths
     */
    private void constructPath(TreeNode root, String path, List<String> listPaths) {
        if (root != null) {
            StringBuffer pathStringBuffer = new StringBuffer(path);
            pathStringBuffer.append(Integer.toString(root.val));
            if (root.left == null && root.right == null) {
                listPaths.add(pathStringBuffer.toString());
            }else {
                pathStringBuffer.append("->");
                constructPath(root.left, pathStringBuffer.toString(), listPaths);
                constructPath(root.right, pathStringBuffer.toString(), listPaths);
            }
        }
    }
}

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
42

_257二叉树的所有路径_递归回溯同时进行

package 代码随想录.树.二叉树;

import 代码随想录.树.TreeNode;

import java.util.ArrayList;
import java.util.List;

public class _257二叉树的所有路径_递归回溯同时进行 {
    public List<String> binaryTreePaths(TreeNode root) {
        List<String> listPaths = new ArrayList<String>();
        if (root == null) {
            return listPaths;
        }
        List<Integer> paths = new ArrayList<Integer>();
        dfsTraversal(root, paths, listPaths);
        return listPaths;
    }

    /**
     *
     * @param root
     * @param paths
     * @param listPaths
     */
    private void dfsTraversal(TreeNode root, List<Integer> paths, List<String> listPaths) {
        paths.add(root.val);
        if (root.left == null && root.right == null) {
            StringBuilder stringBuilder = new StringBuilder();
//            for (int path : paths) {
//                stringBuilder.append(path).append("->");
//            }
            for (int i = 0; i < paths.size() - 1; i++) {
                stringBuilder.append(paths.get(i)).append("->");
            }
            stringBuilder.append(paths.get(paths.size() - 1));
            listPaths.add(stringBuilder.toString());
            return;
        }
        if (root.left!= null) {
            dfsTraversal(root.left, paths, listPaths);
            paths.remove(paths.size() - 1);
        }
        if (root.right!= null) {
            dfsTraversal(root.right, paths, listPaths);
            paths.remove(paths.size() - 1);
        }
    }
}

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
42
43
44
45
46
47
48
49

错误经验吸取