题目:

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

引言:

路径总和问题涉及到在二叉树中寻找从根节点到叶子节点的路径,并验证路径上节点值之和是否等于给定的目标值。这个问题在树的遍历中很常见,可以使用深度优先搜索(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是二叉树的高度。解决这个问题有助于理解二叉树的路径和性质,以及如何使用递归来处理树结构。

标签: 编程算法, 编程算法题, 编程算法大全, 编程算法流程, 算法设计与分析, 数据结构与算法, 算法优化, 算法实现, 常见编程算法, 编程算法入门, 编程算法进阶, 编程算法精通