BM29 二叉树中和为某一值的路径(一)

左手的ㄟ右手 2023-10-04 17:43 7阅读 0赞

### 描述 ###

给定一个二叉树root和一个值 sum ，判断是否有从根节点到叶子节点的节点值之和等于 sum 的路径。

1.该题路径定义为从树的根结点开始往下一直到叶子结点所经过的结点

2.叶子节点是指没有子节点的节点

3.路径只能从父节点到子节点，不能从子节点到父节点

4.总节点数目为n

例如：  
给出如下的二叉树， sum=22，

![8ea6d24475cd22c451dcca7fac51ff00.png][]

返回true，因为存在一条路径 25→4→11→2的节点值之和为 22

数据范围：

1.树上的节点数满足 0≤n≤10000

2.每 个节点的值都满足∣val∣≤1000

要求：空间复杂度 O(n)O(n)，时间复杂度 O(n)O(n)

进阶：空间复杂度 O(树的高度)O(树的高度)，时间复杂度 O(n)O(n)

### 示例1 ###

输入：

{5,4,8,1,11,#,9,#,#,2,7},22

返回值：

true

### 示例2 ###

输入：

{1,2},0

返回值：

false

### 示例3 ###

输入：

{1,2},3
    
    返回值：

true

### 示例4 ###

输入：

{},0

返回值：

false

## 代码（左右子树递归求和） ##

import java.util.*;
    
    /*
     * public class TreeNode {
     *   int val = 0;
     *   TreeNode left = null;
     *   TreeNode right = null;
     * }
     */
    
    public class Solution {
        /**
         * 
         * @param root TreeNode类 
         * @param sum int整型 
         * @return bool布尔型
         */
        boolean flag=false;
        void dfs(TreeNode root ,int s,int sum){
            if(root==null){  //到达叶子节点，就返回递归
                return;
            }
            s=s+root.val;
            if(root.left==null&&root.right==null&&s==sum){  //到达叶子节点
                flag=true;  //如果和等于sum
            }
            else{//如果没有到达叶子节点，左右子树递归
                if(root.left!=null) dfs(root.left,s,sum);
                if(root.right!=null) dfs(root.right,s,sum);
            }
        }
        public boolean hasPathSum (TreeNode root, int sum) {
            // write code here
           dfs(root,0,sum);
            return flag;
        }
    }

[8ea6d24475cd22c451dcca7fac51ff00.png]: https://img-blog.csdnimg.cn/img_convert/8ea6d24475cd22c451dcca7fac51ff00.png