Java算法题-解析 路径总和 算法问题

题目：

给定一个二叉树和一个目标和，判断是否存在从根节点到叶子节点的路径，使得路径上的节点值之和等于目标和。

引言：

路径总和问题涉及到在二叉树中寻找从根节点到叶子节点的路径，并验证路径上节点值之和是否等于给定的目标值。这个问题在树的遍历中很常见，可以使用深度优先搜索（DFS）来解决。

算法思路：

1. 定义一个递归函数 hasPathSum，该函数接受一个二叉树节点和一个目标和作为参数，并返回一个布尔值，表示是否存在路径满足目标和。
2. 在每个节点上，递归调用 hasPathSum 函数来判断左子树和右子树中是否存在路径满足目标和。
3. 在递归的过程中，每次将目标和减去当前节点的值。
4. 如果当前节点是叶子节点（即没有左子树和右子树），则检查目标和是否等于当前节点的值，如果相等则返回 true，否则返回 false。

代码实现：

以下是使用 Java 实现的解决方案：

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int val) {
        this.val = val;
    }
}

public class PathSum {
    public boolean hasPathSum(TreeNode root, int targetSum) {
        if (root == null) {
            return false;
        }

        // 当前节点是叶子节点且值等于目标和，返回 true
        if (root.left == null && root.right == null && root.val == targetSum) {
            return true;
        }

        // 递归检查左子树和右子树
        return hasPathSum(root.left, targetSum - root.val) || hasPathSum(root.right, targetSum - root.val);
    }

    public static void main(String[] args) {
        PathSum solution = new PathSum();

        // 创建一个示例二叉树
        TreeNode root = new TreeNode(5);
        root.left = new TreeNode(4);
        root.right = new TreeNode(8);
        root.left.left = new TreeNode(11);
        root.right.left = new TreeNode(13);
        root.right.right = new TreeNode(4);
        root.left.left.left = new TreeNode(7);
        root.left.left.right = new TreeNode(2);
        root.right.right.right = new TreeNode(1);

        int targetSum = 22;
        boolean hasPath = solution.hasPathSum(root, targetSum);
        System.out.println("是否存在路径满足目标和 " + targetSum + ": " + hasPath);
    }
}

算法分析：

• 时间复杂度：对于每个节点，我们只需遍历一次，因此时间复杂度是O(n)，其中n是二叉树的节点数。
• 空间复杂度：递归调用栈的深度最多为树的高度，所以空间复杂度是O(h)，其中h是二叉树的高度。

示例和测试：

假设给定一个示例二叉树 root 和目标和 targetSum，如下所示：

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

根据算法，我们可以判断是否存在路径满足目标和。我们可以使用以下代码进行测试：

public class Main {
    public static void main(String[] args) {
        PathSum solution = new PathSum();

        TreeNode root = new TreeNode(5);
        root.left = new TreeNode(4);
        root.right = new TreeNode(8);
        root.left.left = new TreeNode(11);
        root.right.left = new TreeNode(13);
        root.right.right = new TreeNode(4);
        root.left.left.left = new TreeNode(7);
        root.left.left.right = new TreeNode(2);
        root.right.right.right = new TreeNode(1);

        int targetSum = 22;
        boolean hasPath = solution.hasPathSum(root, targetSum);
        System.out.println("是否存在路径满足目标和 " + targetSum + ": " + hasPath);
    }
}

总结：

路径总和问题是一个常见的二叉树遍历问题，通过使用深度优先搜索（DFS）来遍历二叉树，同时更新目标和，可以有效地解决这个问题。这个算法的时间复杂度是O(n)，空间复杂度是O(h)，其中n是二叉树的节点数，h是二叉树的高度。解决这个问题有助于理解二叉树的路径和性质，以及如何使用递归来处理树结构。