简：二叉树分支求和

145 阅读 0 评论 96 点赞

我是靠谱客的博主坚强小熊猫，这篇文章主要介绍简：二叉树分支求和，现在分享给大家，希望可以做个参考。

题目描述

给定一个二叉树和一个值 sum sum，判断是否有从根节点到叶子节点的节点值之和等于 sum sum的路径，
例如：
给出如下的二叉树， sum=22 sum=22，

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

解：

这道题主要考察二叉树的深度遍历，这道题要避免多余的查找，一旦找到符合的就直接返回结束递归。

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
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布尔型
     */
    private int s=0;
    
    public boolean find(TreeNode node,int sum){
        s+=node.val;
        if(node.left==null && node.right==null && s==sum){
            return true;
        }
        if(node.right!=null && find(node.right,sum)){
            return true;
        }
        if(node.left!=null && find(node.left,sum)){
            return true;
        }
        s-=node.val;
        return false;
    }
    
    
    public boolean hasPathSum (TreeNode root, int sum) {
        //注意null+0的组合，数学逻辑上来讲“没有=0”也没问题
        //但这道题的测试用例null表示无，也就不存在sum，也就不会=0
        if(root==null){
            return false;
        }
        return find(root,sum);
    }
}