路径总和 Posted on 2021-06-21 00:00:00 2021-06-26 00:00:00 by Author 摘要 给一颗二叉树，并且给定一个固定的值，你能判断该树中是否存在根节点到叶子节点 的路径和等于该固定值吗？？？？？？ # 路径总和 1. 题目描述 - 给你二叉树的根节点 root 和一个表示目标和的整数 targetSum ，判断该树中是否存在 根节点到叶子节点 的路径，这条路径上所有节点值相加等于目标和 targetSum 。叶子节点 是指没有子节点的节点。 2. 示例描述 - 示例一 - 输入：[5,4,8,11,null,13,4,7,2,null,null,null,1], targetSum = 22  - 输出：true - 示例二 - 输入：root = [1,2,3], targetSum = 5  - 输出：false - 示例三 - 输入：root = [1,null,2,null,null,3,null], targetSum = 5  - 输出：true 3. 解题思路 - 对于这道题是查找二叉树所有的路径的变形题目，大家可以看看[二叉树的所有路径](http://www.geticsen.cn/view/articles/detail/bf44119c-de72-4c8d-964c-25970e6a7d67 "二叉树的所有路径")这篇文章，看完之后再来品味这道题目，就能体会到有那味了。首先本题要求是在所给的二叉树中每条路径的节点和等于所给的目标值就说明找到了返回true，如果所有路径都不满足这个要求就返回false。我们前面已经知道寻找二叉树的所有路径的算法了，那我们直接在这个基础上改变一下就可以。 - 首先确定遍历方式，即就是选择前中后遍历的哪种形式。毫无疑问选择前序遍历。因为寻找二叉树的路径就是从前往后找，直到找到叶子节点，那么这条路径就找到了，符合二叉树的前序遍历的形式。第二步是我们怎么记录沿途访问节点的总和尼，这里又牵扯了`回溯`的思想，我们可以在递归的过程中用一个临时变量记录遍历过程中到该节点的时候沿途访问节点的总和，如果该节点是叶子节点的话，那么就在判断这条路径的和(即临时变量的值)与所给的目标值是否一样，如果一样说明就找到了直接返回true，不用再遍历其他的路径，否则就遍历其他的路径，如果整个树的所有路径都不满足，就返回false。 - 这里用到的`回溯思想`从哪里体现尼？首先我们想假如一个节点下有两条路径，如果左路径不满足要求，那么还需要判断右路径是否满足当前的要求，所以要从左路径的那种状态回溯到要遍历该节点右路径的那种状态，对于每一个节点都需要这种做法，所以这里用来回溯加递归的思想去解决这道题目。具体代码如下所示。 4. 代码示例 ```java public boolean hasPathSum(TreeNode root, int targetSum) { //递归回溯去寻找是否满足该题目要求的一条路径 return trackBack(root,targetSum,0); } public boolean trackBack(TreeNode root, int targetSum, int tempSum) { //前序遍历的一般写法 if (root != null) { //如果是叶子节点 if (root.left == null && root.right == null) { //判断该路径的和是否等于目标值，如果等于目标值就返回true //这里为什么临时变量值还要加上该节点的值尼， //因为到达这一层，该临时变量没有算上该节点的值，所以假设该节点的值，才算整条路径的值 if (tempSum + root.val == targetSum) return true; //否则就返回false else return false; } //前序变量的一般写法 //不管左路径还是右路经，只要其中的某一条路径满足当前题目的要求，就说明找到一条路径，返回true //这里回溯的思想在哪体现尼 //在tempSum + root.val这里，为什么尼因为我们直到tempResult是局部变量 //那么在递归返回到该步骤的时候，tempResult就是记录当时调用时的值，就达到回溯的思想 if (trackBack(root.left, targetSum, tempSum + root.val) || trackBack(root.right, targetSum, root.val + tempSum)) { return true; } //如果以上不理解，可以写成一下的形式 /** * //到达该节点，把当前路径的值记录下来 * tempSum = tempSum + root.val; * //继续访问该节点左路径或者右路径 ，如果有一条满足的就返回true * if (trackBack(root.left, targetSum, tempSum) || trackBack(root.right, targetSum, tempSum)) { * return true; * } * //该节点不满，就回溯到第一此访问该节点时的状态 * tempSum = tempSum - root.val; */ } //遍历完整棵二叉树都没找到一条路径满足题目的要求的，就返回false return false; } ```
{{ item.content }}
{{ child.content }}