二叉树中是否存在节点和为指定值的路径

曾经终败给现在 2022-12-04 04:27 158阅读 0赞

# 二叉树中是否存在节点和为指定值的路径 #

## 1、从根节点到叶子节点 ##

### 1.1、参考资料 ###

https://www.nowcoder.com/practice/508378c0823c423baa723ce448cbfd0c

### 1.2、题目要求 ###

给定一个二叉树和一个值 `target`，判断是否有从根节点到叶子节点的节点值之和等于 `target` 的路径，例如：给出如下的二叉树，`target=22`，程序运行返回 `true`，因为存在一条路径 `5 ---> 4 ---> 11 ---> 2`，其节点路径值为 `22`

![image-20200905152506228][]

### 1.3、代码思路 ###

题目的思路

1.  看到二叉树的路径问题，多半都是用 `dfs`，首先我们需要明确题目的意思：从根节点出发，到叶子节点停止
2.  递归难就难在：我们在还未编写完成 `dfs()` 函数时，就需要明确这个函数到底需要完成什么功能？参数有哪些？返回值代表什么含义？这些只有在写递归函数的时候，一步一步摸索出来
3.  我们现在假定 `boolean dfs(TreeNode curNode, int target)` 函数的作用为：接收一个节点 `curNode`，接受一个路径的目标值 `target`，返回从该节点到叶子节点是否存在目标路径，使得路径的值等于 `target`

--------------------

好了，现在明确了函数的作用之后，现在可以编写函数的逻辑了

1.  首先，深度优点遍历来说，想都不用想，上来直接先写上一个回溯 `if (curNode == null) { return false; }`，这表示递归至最深层开始回溯，至于为什么 `return false` 后面再讲
2.  每次进入函数时，将 `target` 减去当前节点的权重(`curNode.val`)，当 `target` 减到零时，说明目标路径存在，另外我们的目标是到叶子节点停止，叶子节点的条件是 `curNode.left == null && curNode.right == null`，所以说当 `if (curNode.left == null && curNode.right == null && target == 0) {`，我们返回 `true` 表示找到目标路径
3.  深度遍历的分支：对于当前节点 `curNode` 有两个分支，这两个分支都有可能成为目标路径，所以深度优先遍历的写法为 `return dfs(curNode.left, target) || dfs(curNode.right, target);`
4.  现在来谈谈为什么回溯时需要返回 `false`，因为当 `curNode` 为叶子节点时，并且 `target == 0` 时，我们已经返回了 `true`，剩下的情况就是 `curNode` 不是叶子节点或者路径值不为 `target`，所应该返回 `false'`

### 1.4、代码实现 ###

代码

public class Solution {
        
    
        public boolean hasPathSum(TreeNode root, int target) {
        
            // Guard Safe
            if (root == null) {
        
                return false;
            }
            // 深度优先遍历
            return dfs(root, target);
        }
    
        private boolean dfs(TreeNode curNode, int target) {
        
            // 目标路径不存在，开始回溯
            if (curNode == null) {
        
                return false;
            }
            // 更新目标值
            target -= curNode.val;
            // 当当前节点为叶子节点并且目标路径存在时，返回 true
            if (curNode.left == null && curNode.right == null && target == 0) {
        
                return true;
            }
            // 对左右分支进行 dfs
            return dfs(curNode.left, target) || dfs(curNode.right, target);
        }
    }
    
    public class TreeNode {
        
        int val = 0;
        TreeNode left = null;
        TreeNode right = null;
    }

## 2、从任意节点到叶子节点 ##

### 2.1、题目要求 ###

判断是否有从任意节点到叶子节点的节点值之和等于 `target` 的路径，

### 2.2、代码思路 ###

1.  因为要判断当前节点到叶子节点的是否存在目标路径，所以 `boolean dfs(TreeNode curNode, int target) {` 函数还是和上面的一样
2.  由于需要以树中的每个节点(`root`)作为根节点，判断以 `root` 作为根节点的子树是否存在目标路径，这也需要进行递归，`boolean hasPathSum(TreeNode root, int target) {` 函数便实现了此功能
3.  `boolean hasPathSum(TreeNode root, int target) {` 函数先判断 `root` 节点到叶子节点是否存在目标路径；然后进行左递归：判断以 `root.left` 为根节点的子树是否存在目标路径；然后进行右递归：判断以 `root.right` 为根节点的子树是否存在目标路径

### 2.3、代码实现 ###

代码

public class Solution {
        
        public boolean hasPathSum(TreeNode root, int target) {
        
            // Guard Safe
            if (root == null) {
        
                return false;
            }
            // 1.判断 root 节点到叶子节点是否存在目标路径
            // 2.以 root.left 为根节点的子树是否存在目标路径
            // 3.以 root.right 为根节点的子树是否存在目标路径
            return dfs(root, target) || hasPathSum(root.left, target) || hasPathSum(root.right, target);
        }
    
        private boolean dfs(TreeNode curNode, int target) {
        
            // 目标路径不存在，开始回溯
            if (curNode == null) {
        
                return false;
            }
            // 更新目标值
            target -= curNode.val;
            // 当当前节点为叶子节点并且目标路径存在时，返回 true
            if (curNode.left == null && curNode.right == null && target == 0) {
        
                return true;
            }
            // 对左右分支进行 dfs
            return dfs(curNode.left, target) || dfs(curNode.right, target);
        }
    }
    
    public class TreeNode {
        
        int val = 0;
        TreeNode left = null;
        TreeNode right = null;
    }

## 3、从任意节点到任意节点 ##

### 3.1、题目要求 ###

判断是否有从任意节点到任意节点的节点值之和等于 `target` 的路径，

### 3.2、代码思路 ###

额，`boolean dfs(TreeNode curNode, int target) {` 函数的实现逻辑需要改变，我们不需要走到叶子节点，走到任意一个节点，只要路径存在，则返回 `true`

### 3.3、代码实现 ###

代码

public class Solution {
        
    
        public boolean hasPathSum(TreeNode root, int target) {
        
            // Guard Safe
            if (root == null) {
        
                return false;
            }
            // 1.判断 root 节点到叶子节点是否存在目标路径
            // 2.以 root.left 为根节点的子树是否存在目标路径
            // 3.以 root.right 为根节点的子树是否存在目标路径
            return dfs(root, target) || hasPathSum(root.left, target) || hasPathSum(root.right, target);
        }
    
        private boolean dfs(TreeNode curNode, int target) {
        
            // 目标路径不存在，开始回溯
            if (curNode == null) {
        
                return false;
            }
            // 更新目标值
            target -= curNode.val;
            // 当当前节点为叶子节点并且目标路径存在时，返回 true
            if (target == 0) {
        
                return true;
            }
            // 对左右分支进行 dfs
            return dfs(curNode.left, target) || dfs(curNode.right, target);
        }
    
    }
    
    public class TreeNode {
        
        int val = 0;
        TreeNode left = null;
        TreeNode right = null;
    }

[image-20200905152506228]: /images/20221123/99453f12d77548d4974da09456b3c99c.png