My code:
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class Solution {
public boolean hasPathSum(TreeNode root, int sum) {
if (root == null)
return false;
return hasPathSum(root, 0, sum);
}
private boolean hasPathSum(TreeNode root, int sum, int totalSum) {
if (root == null)
return false;
if (root.left == null && root.right == null) {
if (sum + root.val == totalSum)
return true;
else
return false;
}
else
return hasPathSum(root.left, sum + root.val, totalSum) | hasPathSum(root.right, sum + root.val, totalSum);
}
}
My test result:
我的算法不是很好，但是勉强凑活吧。
就是一个DFS。
**
总结： Tree DFS
**
Anyway, Good luck, Richardo!
My code:
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class Solution {
public boolean hasPathSum(TreeNode root, int sum) {
if (root == null) {
return false;
}
return helper(root, 0, sum);
}
private boolean helper(TreeNode root, int curr, int sum) {
if (root.left == null && root.right == null) {
if (curr + root.val == sum) {
return true;
}
else {
return false;
}
}
else {
if (root.left != null) {
boolean flag = helper(root.left, curr + root.val, sum);
if (flag) {
return true;
}
}
if (root.right != null) {
boolean flag = helper(root.right, curr + root.val, sum);
if (flag) {
return true;
}
}
return false;
}
}
}
简单题，没什么好说的。
Anyway, Good luck, Richardo! -- 08/28/2016
