每日一道JAVA算法题:寻找二叉树中路径和为给定值的所有路径

题目描述：

给定一棵二叉树和一个整数sum，找出所有从根节点到叶节点的路径，这些路径上所有节点值的和等于sum。

例如，给定如下二叉树和sum=22，应返回：

      5
     / \
    4   8
   /   / \
  11  13  4
 /  \    / \
7    2  5   1

[
   [5,4,11,2],
   [5,8,4,5]
]

解题思路：

这道题可以使用深度优先搜索（DFS）来解决。具体来说，从根节点开始，依次遍历每一个节点，并记录从根节点到该节点的路径，如果该节点是叶节点且路径和等于sum，则将该路径添加到结果列表中。否则，递归遍历该节点的左右子树，将当前节点从路径中移除，然后回溯到上一级节点继续遍历。

Java代码实现如下：

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

public class Solution {
    public List<List<Integer>> pathSum(TreeNode root, int sum) {
        List<List<Integer>> result = new ArrayList<>();
        if (root == null) {
            return result;
        }
        List<Integer> path = new ArrayList<>();
        dfs(root, sum, path, result);
        return result;
    }

    private void dfs(TreeNode node, int sum, List<Integer> path, List<List<Integer>> result) {
        // 将当前节点添加到路径中
        path.add(node.val);
        // 如果是叶节点且路径和等于sum，则将该路径添加到结果列表中
        if (node.left == null && node.right == null && sum == node.val) {
            result.add(new ArrayList<>(path));
        } else {
            // 否则，继续遍历左右子树
            if (node.left != null) {
                dfs(node.left, sum - node.val, path, result);
            }
            if (node.right != null) {
                dfs(node.right, sum - node.val, path, result);
            }
        }
        // 回溯到上一级节点，将当前节点从路径中移除
        path.remove(path.size() - 1);
    }
}

其中，TreeNode 是二叉树节点的定义：

public class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}

这道题的时间复杂度为 O(nlogn)，其中 n 是二叉树的节点数。因为我们需要遍历二叉树的所有节点，每次遍历的时间复杂度是 O(logn)，最坏情况下需要遍历所有的叶节点，因此总时间复杂度为 O(nlogn)。