你的位置:首页 > Java教程

[Java教程]112. Path Sum


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   1
return true, as there exist a root-to-leaf path 5->4->11->2 which sum is 22.

 1 /** 2  * Definition for a binary tree node. 3  * public class TreeNode { 4  *   int val; 5  *   TreeNode left; 6  *   TreeNode right; 7  *   TreeNode(int x) { val = x; } 8  * } 9 */10 public class Solution {11   public boolean hasPathSum(TreeNode root, int sum) {12     boolean flag=false;13     14     if(root==null)15     return false;16     17     if(root.left==null&&root.right==null&&root.val==sum)18     {19     flag=true;20     return flag;21     }22     23     if(root.left!=null||root.right!=null)24     {25       if(root.left!=null&&flag==false)26       {27       flag=hasPathSum(root.left,sum-root.val);  28       if(flag==true)29       return flag;30       }31       32       if(root.right!=null&&flag==false)33       {34       flag=hasPathSum(root.right,sum-root.val);  35       if(flag==true)36       return flag;37       }38       39     }40     return flag;41   }42 }

 

      4  8      /  / \     11 13 4     / \   \    7  2   1

return true, as there exist a root-to-leaf path 5->4->11->2 which sum is 22.

代码如下: