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.leftnullnode.rightnullcount0)returntrue;if(node.leftnullnode.rightnull)returnfalse;// 处理左节点if(node.left!null){count-node.left.val;// 递归处理结果if(traversal(node.left,count))returntrue;countnode.left.val;// 回溯}// 处理右节点if(node.right!null){count-node.right.val;// 递归处理结果if(traversal(node.right,count))returntrue;countnode.right.val;// 回溯}returnfalse;}publicbooleanhasPathSum(TreeNoderoot,inttargetSum){if(rootnull)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(rootnull)returnfalse;// 迭代终止条件if(root.leftnullroot.rightnull)returntargetSumroot.val;returnhasPathSum(root.left,targetSum-root.val)||hasPathSum(root.right,targetSum-root.val);}}