leetcode - 257. 二叉树的所有路径

257. 二叉树的所有路径

题目

解决

做法一：深度优先搜索 + 回溯

        深度优先搜索（Depth-First Search, DFS）是一种用于遍历或搜索树或图的算法。这种搜索方式会尽可能深地探索每个分支，直到无法继续深入为止，然后回溯到上一个节点，继续探索其他未访问的分支。

        回溯我的个人理解是回退到之前的状态

        大致想法：就是使用递归，在递归过程中使用 StringBuilder 存储路径上的节点和 箭头指向字符，直到 TreeNode 节点中左子节点 和 右子节点 都为空，将 StringBuilder 中存的依赖路径 加入到 list 中，每当退出递归，就回溯（将加入的 （节点值 + "->"） 删除掉）

/**
 * 执行用时分布 5 ms 击败 30.20% 复杂度分析 消耗内存分布 41.53 MB 击败 70.56%
 */
public List<String> binaryTreePaths(TreeNode root) {
    List<String> list = new ArrayList<>();
    StringBuilder path = new StringBuilder();
    path.append(root.val);
    // 递归获取 根节点到 叶子节点的路径
    getPath(root, path, list);
    return list;
}

/**
 * 递归获取 根节点到 叶子节点的路径
 */
public void getPath(TreeNode root, StringBuilder path, List<String> list) {
    // 递归边界就是 叶子节点，碰到叶子节点则递归结束，并将叶子节点的路径加入到结果集
    if (root.left == null && root.right == null){
        list.add(path.toString());
        return;
    }
    if (root.left != null){
        String pathStr = "->" + root.left.val;
        // 将 左子树节点的值加入到 树路径中
        path.append(pathStr);
        // 递归左子树
        getPath(root.left, path, list);
        // 回溯，将当前节点的左节点剔除出 字符串
        path.delete(path.length() - pathStr.length(), path.length());
    }
    if (root.right != null){
        String pathStr = "->" + root.right.val;
        path.append(pathStr);
        getPath(root.right, path, list);
        path.delete(path.length() - pathStr.length(), path.length());
    }
}

优化

        做法上基本是这样，但是时间上呢还是太慢了，根据以往经验发现可以将字符串替换成 栈 这个数据结构，弹出一个节点，可比 StringBuilder 删除来得快，StringBuilder.delete 底层是将整个字符数组拷贝的，相比于 栈 他是先进后出的，从栈顶弹出元素相对较快。

        Deque 参考链接：双端队列 【Deque】-CSDN博客

时间复杂度：O(nlogn)；空间复杂度：O(nlogn)

因为遍历到叶子节点之后，还需要遍历 栈，最环的情况是 叶子节点的数量为 n/2，每个路径字符串的长度为 log(n)（因为完全二叉树的高度为 log(n)）

/**
 * 执行用时分布 3 ms 击败 33.70% 复杂度分析 消耗内存分布 41.55 MB 击败 64.43%
 */
public List<String> binaryTreePaths(TreeNode root) {
    List<String> list = new ArrayList<>();
    // 双端队列
    Deque<Integer> path = new LinkedList<>();
    // 递归获取 根节点到 叶子节点的路径
    getPath(root, path, list);
    return list;
}

/**
 * 递归获取 根节点到 叶子节点的路径
 */
public void getPath(TreeNode root, Deque<Integer> path, List<String> list) {
    if (root == null){
        return;
    }
    if (root.left == null && root.right == null){
        StringBuilder builder = new StringBuilder();
        // 遍历，组合成路径字符串
        path.forEach(val -> {
            builder.append(val).append("->");
        });
        // 加入当前叶子节点的 值
        builder.append(root.val);
        list.add(builder.toString());
        return;
    }
    // 因为回溯需要将，当前节点弹出并且需要按顺序循环遍历出来，所以选用 尾部插入，尾部弹出
    // 将当前节点加入
    path.add(root.val);
    // 递归左子树
    getPath(root.left, path, list);
    // 递归右子树
    getPath(root.right, path, list);
    // 回溯
    path.removeLast();
}

做法二：深度优先搜索

参考官解：. - 力扣（LeetCode）

这里相对于上面快，是因为这里不需要回溯，使用的是局部变量

/**
 * 参考官解：https://leetcode.cn/problems/binary-tree-paths/solutions/400326/er-cha-shu-de-suo-you-lu-jing-by-leetcode-solution/
 * 深度优先遍历解法
 * 执行用时分布 1 ms 击败 99.56% 复杂度分析 消耗内存分布 41.57 MB 击败 58.89%
 */
public List<String> binaryTreePaths(TreeNode root) {
    List<String> list = new ArrayList<>();
    // 递归获取 根节点到 叶子节点的路径
    getPath(root, "", list);
    return list;
}

/**
 * 递归获取 根节点到 叶子节点的路径
 */
public void getPath(TreeNode root, String path, List<String> list) {
    if (root == null){
        return;
    }
    StringBuilder builder = new StringBuilder(path);
    builder.append(root.val);
    if (root.left == null && root.right == null){
        list.add(builder.toString());
        return;
    }
    builder.append("->");
    // 递归左子树
    getPath(root.left, builder.toString(), list);
    // 递归右子树
    getPath(root.right, builder.toString(), list);
}

做法三：广度优先遍历

广度优先遍历

        广度优先遍历（Breadth-First Search, BFS）是一种用于图或树的遍历算法。这种搜索方式从根节点（或任意一个起始节点）开始，逐层访问每个节点的邻居节点，直到所有可达节点都被访问到。BFS 的特点是先访问离起点最近的节点，然后再逐步向外扩展。

/**
 * 宽度遍历/广度优先遍历
 * @param head
 */
private static void levelOrder(Node head){
    if (head == null) {
        return;
    }
    Queue<Node> queue = new LinkedList<>();
    queue.offer(head);
    while (!queue.isEmpty()){
        head = queue.poll();
        System.out.print(head.value + " ");
        if (head.left != null){
            queue.offer(head.left);
        }
        if (head.right != null){
            queue.offer(head.right);
        }
    }
}

代码

/**
 * 广度优先搜索
 * 执行用时分布 2 ms 击败 47.70% 复杂度分析 消耗内存分布 41.48 MB 击败 79.08%
 */
public List<String> binaryTreePaths(TreeNode root) {
    // 存储结果集
    List<String> result = new ArrayList<>();

    // 用于遍历存储节点
    Queue<TreeNode> nodeQueue = new LinkedList<>();
    // 用于存储 nodeQueue 的依赖路径
    Queue<String> pathQueue = new LinkedList<>();

    // 先将 根节点 加入队列用于遍历
    nodeQueue.add(root);
    // 将路径同步加入
    pathQueue.add(Integer.toString(root.val));

    // 遍历知道所有节点为空
    while (!nodeQueue.isEmpty()){
        // 弹出节点和路径
        TreeNode node = nodeQueue.poll();
        String path = pathQueue.poll();

        // 叶子节点
        if (node.left == null && node.right == null) {
            result.add(path);
            continue;
        }

        // 如果左子节点不为空就将节点加入到队列中，并将依赖路径拼接好加入队列
        if (node.left != null){
            nodeQueue.add(node.left);
            pathQueue.add(new StringBuilder(path).append("->").append(node.left.val).toString());
        }

        if (node.right != null){
            nodeQueue.add(node.right);
            pathQueue.add(new StringBuilder(path).append("->").append(node.right.val).toString());
        }
    }
    return result;
}