[数据结构与算法]March.31.2022——112. 路径总和

March.31.2022——112. 路径总和

题目描述

112. 路径总和

力扣题目链接(opens new window)

给定一个二叉树和一个目标和，判断该树中是否存在根节点到叶子节点的路径，这条路径上所有节点值相加等于目标和。

说明: 叶子节点是指没有子节点的节点。

解题思路

• 最初我的思路是 再递归的时候把路径上每个节点的val值进行累加，再进行判断，如果累加和等于target的话就返回true
• 但是这样代码会比较麻烦
• 可以用递减，让计数器count初始为目标和，然后每次减去遍历路径节点上的数值。
• 如果最后count == 0，同时到了叶子节点的话，说明找到了目标和。
• 如果遍历到了叶子节点，count不为0，就是没找到。

代码实现

class Solution {
    public boolean hasPathSum(TreeNode root, int targetSum) {
        //1.确定递归条件
        if(root == null){
            return false;
        }
        //2.根据确定的返回值写递归函数
        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);
    }
}