leetcode 112.PathSum

2017-08-02

题意

计算二叉树路径累加值中和目标值相等

我的想法

递归实现，遍历整个树。计算出所有路径的值，计算到有相等的就暂停、

两个坑

可能是节点上可能是负数，所以不能通过判断当前和大于目标值来减少遍历的次数
必须到叶子节点上才能算一条完整的路线，半途中达到目标值不算。

boolean flag = false;
  public boolean hasPathSum(TreeNode root, int sum) {
      if(root==null) return false;
      helper(root,0,sum);
      return flag;
  }
  public int helper(TreeNode node,int s,int sum){
      if(node==null) return s;
      s += node.val;
      if(node.left==null&&node.right==null&&s==sum) {flag = true;return s;}
      if(!flag) helper(node.left,s,sum);
      if(!flag) helper(node.right,s,sum);
      return s;
  }

大神代码

反向思维。题目中提到路径上相加等于目标值，会让人产生一定要通过相加得到该值。然而大神通过减去节点值，实现了在hasPathSum函数的递归，仅用三行代码解决了问题。

public class Solution {
    public boolean hasPathSum(TreeNode root, int sum) {
        if(root == null) return false;
        if(root.left == null && root.right == null && sum - root.val == 0) return true;
        return hasPathSum(root.left, sum - root.val) || hasPathSum(root.right, sum - root.val);
    }
}