您现在的位置是：首页 > 后台技术 > 数据结构与算法数据结构与算法

路径总和(图文)

第十三双眼睛2023-11-28【数据结构与算法】人已围观

简介路径总和
给你二叉树的根节点 root 和一个表示目标和的整数 targetSum 。判断该树中是否存在根节点到叶子节点的路径，这条路径上所有节点值相加等于目标和 targetSum 。如果存在，返回 true ；否则，返回 false 。

思路：利用广度优先搜索算法，从根节点开始，建立两个队列，一个用来存放节点，一个用来存放当前路径总和，循环判断，如果当前节点是根节点，则看对应的路径总和与目标值是否相等，如果相等，则返回true，如果不相等，如果不相等，则继续遍历其他节点。如果不是叶子节点，则判断左右节点是否存在，如果存在，则把对应的节点放入节点队列，把路径和加上对应节点的值放入路径和队列，当循环跳出时，如果还没有找到等于目标和的路径，就返回false。代码如下：

public static boolean method1(TreeNode root,int targetSum) {
   if (root == null) {
       return false;
   }
   Queue<TreeNode> nodeQueue = new LinkedList<TreeNode>();
   Queue<Integer> valueQueue = new LinkedList<>();
   nodeQueue.offer(root);
   valueQueue.offer(root.val);
   while (!nodeQueue.isEmpty()) {
       TreeNode tempNode = nodeQueue.poll();
       Integer sumValue = valueQueue.poll();
       // 如果已经是根节点了,判断和是不是等于目标值,如果等于,直接返回
       if (tempNode.left == null && tempNode.right == null) {
           if (sumValue.intValue() == targetSum) {
               return true;
           }
       }
       if (tempNode.left != null) {
           nodeQueue.offer(tempNode.left);
           valueQueue.offer(tempNode.left.val + sumValue);
       }
       if (tempNode.right != null) {
           nodeQueue.offer(tempNode.right);
           valueQueue.offer(tempNode.right.val + sumValue);
       }
   }
   // 如果循环完了,还没有找到,那就是没有
   return false;
}

思路二：假定从根节点到当前节点的值之和为 val，我们可以将这个大问题转化为一个小问题：是否存在从当前节点的子节点到叶子的路径，满足其路径和为 sum - val。代码如下：

public static boolean method2(TreeNode root,int targetSum) {
   if (root == null) {
       return false;
   }
   // 如果是根节点,就判断当前的值是否与目标值相等
   if (root.left == null && root.right == null) {
       return targetSum == root.val;
   }
   return method1(root.left, targetSum - root.left.val) || method1(root.right, targetSum - root.right.val);
}

Tags：

很赞哦！ ()

上一篇：二叉树的最小深度(图文)

下一篇：杨辉三角(图文)