Given a binary tree and a sum, determine if the tree has a root-to-leaf path such that adding up all the values along the path equals the given sum.
For example:
Given the below binary tree and
sum = 22
,
5 / \ 4 8 / / \ 11 13 4 / \ \ 7 2 1return true, as there exist a root-to-leaf path
5->4->11->2
which sum is 22.A:
-------------------第二遍-------------------
public class Solution { public boolean hasPathSum(TreeNode root, int sum) { if(root == null) return false; if(root.left == null && root.right == null) return root.val == sum; if(root.left != null && hasPathSum(root.left, sum-root.val)) return true; if(root.right != null && hasPathSum(root.right, sum-root.val)) return true; return false; } }
----------3 rd pass ---------下面的这个代码是不对的,为什么呢?-----
public class Solution { public boolean hasPathSum(TreeNode root, int sum) { if(root==null) return false; return helper(root,sum); } private boolean helper(TreeNode root, int sum){ if(root ==null) return sum==0; return helper(root.left, sum-root.val) || helper(root.right,sum-root.val); } }
Mistakes:
1 :因为,对leaf的理解不对,只有当某个节点没有child的时候,它才是leaf。
而上面的方法,会让不是leaf的节点被当作节点
2: 即使是boolean类型的,要用的时候,也要 先显著的声明下,而不能用它的默认值。
(貌似避免不同平台的默认值不同)
Learned:
No comments:
Post a Comment