LeetCode 112. 路径总和 II java题解
https://leetcode.cn/problems/path-sum/description/
class Solution {
boolean res=false;//记录结果
public boolean hasPathSum(TreeNode root, int targetSum) {
if(root==null) return res;
int sum=0;
find(root,sum,targetSum);
return res;
}
public void find(TreeNode root,int sum,int target){
if(root==null) return;
//节点不为空。将节点值加入和
sum+=root.val;
//节点是叶子结点,并且和是目标和,找到结果
if(sum==target&&root.left==null&&root.right==null){
res=true;
return;
}
//不是叶子结点
if(root.left!=null){
find(root.left,sum,target);
}
if(root.right!=null){
find(root.right,sum,target);
}
}
}
/*
遍历顺序,根左右,带入和遍历下一层。
到叶子结点时,判断和,如果和=target,返回true
*/
别人的代码
class solution {
public boolean haspathsum(treenode root, int targetsum) {
if (root == null) {
return false;
}
targetsum -= root.val;
// 叶子结点
if (root.left == null && root.right == null) {
return targetsum == 0;
}
if (root.left != null) {
boolean left = haspathsum(root.left, targetsum);
if (left) { // 已经找到
return true;
}
}
if (root.right != null) {
boolean right = haspathsum(root.right, targetsum);
if (right) { // 已经找到
return true;
}
}
return false;
}
}
// lc112 简洁方法
class solution {
public boolean haspathsum(treenode root, int targetsum) {
if (root == null) return false; // 为空退出
// 叶子节点判断是否符合
if (root.left == null && root.right == null) return root.val == targetsum;
// 求两侧分支的路径和
return haspathsum(root.left, targetsum - root.val) || haspathsum(root.right, targetsum - root.val);
}
}