货车保险哪家网站可以直接做/用模板快速建站

一、题目

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

叶子节点 是指没有子节点的节点。

链接：https://leetcode-cn.com/problems/path-sum

二、答案

DFS:对于树来说DFS即为先序遍历。

class TreeNode {int val;TreeNode left;TreeNode right;TreeNode() {}TreeNode(int val) { this.val = val; }TreeNode(int val, TreeNode left, TreeNode right) {this.val = val;this.left = left;this.right = right;}}class PathSum {/*** dfs** @param root* @param targetSum* @return*/public boolean hasPathSum(TreeNode root, int targetSum) {if (root == null){return false;}if (root.left == null && root.right == null){return targetSum == root.val;}boolean left = hasPathSum(root.left, targetSum - root.val);boolean right = hasPathSum(root.right, targetSum -  root.val);return left || right;}}

回溯:深度遍历的一种情况，暴力搜索所有路径。

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
class Solution {List<List<Integer>> result = new ArrayList<>();public List<List<Integer>> pathSum(TreeNode root, int targetSum) {if (root == null){return new ArrayList<>();}List<Integer> visited = new ArrayList<>();backTrace(visited, root,targetSum);List<List<Integer>> pathes = new ArrayList<>();for (List<Integer> path : result) {if(isTargetNum(path,targetSum)){pathes.add(path);}}return pathes;}private boolean isTargetNum(List<Integer> path, int targetSum) {int sum = 0;for (int i = 0; i < path.size(); i++) {sum += path.get(i);}return sum == targetSum;}private void backTrace(List<Integer> visited, TreeNode root, int targetSum) {if (root == null){return;}visited.add(root.val);if (root.right == null && root.left == null) {result.add(new ArrayList<>(visited));visited.remove(visited.size() - 1);return;}backTrace(visited,root.left,targetSum);backTrace(visited,root.right,targetSum);visited.remove(visited.size() - 1);}
}

BFS:对于树来说为层次遍历。关键点在于增加一个存所有sum的队列。

import java.util.LinkedList;
import java.util.Queue;class PathSumBfs {/*** bfs** @param root* @param targetSum* @return*/public boolean hasPathSum(TreeNode root, int targetSum) {if (root == null){return false;}Queue<TreeNode> queue = new LinkedList<>();queue.offer(root);Queue<Integer> sumQue = new LinkedList<>();sumQue.offer(root.val);int sum = 0;while (!queue.isEmpty()){TreeNode treeNode = queue.poll();sum = sumQue.poll();if (treeNode.left == null && treeNode.right == null){if (sum == targetSum){return true;}continue;}if (treeNode.left != null){queue.offer(treeNode.left);sumQue.offer(sum + treeNode.left.val);}if (treeNode.right != null){queue.offer(treeNode.right);sumQue.offer(sum + treeNode.right.val);}}return false;}}