企业官网建设流程全解析

asp.net网站结构,赣州人才网赣州九一人才,浦东新区建设工程安全质量监督站网站,qiniu cloud for wordpress题目#xff1a; 给你二叉树的根节点 root 和一个表示目标和的整数 targetSum 。判断该树中是否存在 根节点到叶子节点 的路径#xff0c;这条路径上所有节点值相加等于目标和 targetSum 。如果存在#xff0c;返回 true #xff1b;否则#xff0c;返回 false 。 叶子节点…题目给你二叉树的根节点 root 和一个表示目标和的整数 targetSum 。判断该树中是否存在 根节点到叶子节点 的路径这条路径上所有节点值相加等于目标和 targetSum 。如果存在返回 true 否则返回 false 。叶子节点 是指没有子节点的节点。示例 1输入root [5,4,8,11,null,13,4,7,2,null,null,null,1], targetSum 22输出true解释等于目标和的根节点到叶节点路径如上图所示。示例 2输入root [1,2,3], targetSum 5输出false解释树中存在两条根节点到叶子节点的路径(1 -- 2): 和为 3(1 -- 3): 和为 4不存在 sum 5 的根节点到叶子节点的路径。示例 3输入root [], targetSum 0输出false解释由于树是空的所以不存在根节点到叶子节点的路径。解析这道题使用dfs回溯来解决使用深度优先搜索遍历所有可能的路径在遍历过程中从根节点开始记录当前路径的累加和到达叶子节点时检查路径和是否等于目标值找到一条符合条件的路径就立即返回如何表示路径和从目标值开始每经过一个节点就减去其值检查是否减到0递归终止条件是什么到达叶子节点时判断剩余值是否为0如果当前节点为空返回false如何遍历所有路径对每个非叶子节点分别探索其左子树和右子树使用递归进行深度优先搜索具体代码/** * param {TreeNode} root * param {number} targetSum * return {boolean} */varhasPathSumfunction(root,targetSum){// 1. 处理空树的情况空树没有路径直接返回falseif(!root)returnfalse// 2. 从根节点开始遍历初始sum targetSum - 根节点值// 因为根节点的值已经计入路径和了returntraversal(root,targetSum-root.val)};functiontraversal(node,sum){// 3. 终止条件1到达叶子节点且剩余sum为0// sum 0 表示路径和正好等于targetSum// !node.left !node.right 确保是叶子节点if(sum0!node.left!node.right)returntrue// 4. 终止条件2到达叶子节点但剩余sum不为0// 说明这条路径的和不等于targetSumif(sum!0!node.left!node.right)returnfalse// 5. 递归处理左子树if(node.left){// 5.1 做出选择将左子节点的值从sum中减去sum-node.left.val// 5.2 递归探索左子树if(traversal(node.left,sum)){returntrue// 如果左子树找到符合条件的路径直接返回true}// 5.3 撤销选择回溯恢复sum的值// 因为要尝试右子树需要回到之前的状态sumnode.left.val}// 6. 递归处理右子树if(node.right){// 6.1 做出选择将右子节点的值从sum中减去sum-node.right.val// 6.2 递归探索右子树if(traversal(node.right,sum)){returntrue// 如果右子树找到符合条件的路径直接返回true}// 6.3 撤销选择回溯恢复sum的值sumnode.right.val}// 7. 左右子树都没有找到符合条件的路径返回falsereturnfalse}