简：二叉树分支求和

题目描述

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

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

解：

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

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);
    }
}

最后

以上就是坚强小熊猫为你收集整理的简：二叉树分支求和的全部内容，希望文章能够帮你解决简：二叉树分支求和所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。