LeetCode--112. 路径总和（二叉树）
题目描述
给你二叉树的根节点root和一个表示目标和的整数targetSum。判断该树中是否存在根节点到叶子节点的路径，这条路径上所有节点值相加等于目标和targetSum。如果存在，返回true；否则，返回false。
叶子节点是指没有子节点的节点。
示例 1：
输入：root = [5,4,8,11,null,13,4,7,2,null,null,null,1], targetSum = 22 输出：true 解释：等于目标和的根节点到叶节点路径如上图所示。示例 2：
输入：root = [1,2,3], targetSum = 5 输出：false 解释：树中存在两条根节点到叶子节点的路径： (1 --> 2): 和为 3 (1 --> 3): 和为 4 不存在 sum = 5 的根节点到叶子节点的路径。示例 3：
输入：root = [], targetSum = 0 输出：false 解释：由于树是空的，所以不存在根节点到叶子节点的路径。提示：
- 树中节点的数目在范围
[0, 5000]内 -1000 <= Node.val <= 1000-1000 <= targetSum <= 1000
代码
清晰版本：
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; * } * } */classSolution{publicbooleantraversal(TreeNodenode,intcount){// 遇到叶子结点，进行处理if(node.left==null&&node.right==null&&count==0)returntrue;if(node.left==null&&node.right==null)returnfalse;// 处理左节点if(node.left!=null){count-=node.left.val;// 递归，处理结果if(traversal(node.left,count))returntrue;count+=node.left.val;// 回溯}// 处理右节点if(node.right!=null){count-=node.right.val;// 递归，处理结果if(traversal(node.right,count))returntrue;count+=node.right.val;// 回溯}returnfalse;}publicbooleanhasPathSum(TreeNoderoot,inttargetSum){if(root==null)returnfalse;returntraversal(root,targetSum-root.val);}}简洁版本：
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; * } * } */classSolution{publicbooleanhasPathSum(TreeNoderoot,inttargetSum){if(root==null)returnfalse;// 迭代终止条件if(root.left==null&&root.right==null)returntargetSum==root.val;returnhasPathSum(root.left,targetSum-root.val)||hasPathSum(root.right,targetSum-root.val);}}