题解 | #二叉树中和为某一值的路径(一)#

思路

1. 遍历二叉树
2. 维护一个变量res，res的值为从根节点到当前结点路径中结点值的和
   • 遍历到当前节点时令res加上结点值，再遍历左右子树
3. 当遇到叶子节点时，判断res是否等于sum
   • 若等于则设置r为true
   • 若不等于则继续遍历
4. 当前结点遍历结束后令res减去结点值

代码

public class Solution {

    int res=0;
    boolean r=false;
    public boolean hasPathSum (TreeNode root, int sum) {
        if(root==null) return false;
        digui(root, sum);
        return r;
    }

    public void digui(TreeNode root,int sum){
    //如果当前为空结点，则什么也不干
     if(root==null){
         return ;
     }
     //res加上当前结点的值
     res+=root.val;
     //如果当前节点为叶子结点且res值等于sum，设置r为true
     if(root.right==null&&root.left==null&&res==sum){
         r=true;
     }
     digui(root.left,sum);
     digui(root.right, sum); 
     //遍历完左右子树后更新res值（减去当前结点的值）
     res-=root.val;
    }
}