二叉树求路径总和

题目

给你二叉树的根节点 root 和一个表示目标和的整数 targetSum。
判断该树中是否存在根节点到叶子节点的路径，这条路径上所有节点值相加等于目标和 targetSum。
如果存在，返回 true；否则，返回 false。
叶子节点是指没有子节点的节点。

解题和思路

1. 遍历每一层node，如果node为空，则判断val的值和targetSum是否相等。
2. 如果node不为空，则遍历其中的左右节点，targetSum并且减去这一层的targetSum。
3. 遍历到树的叶子节点，判断当前的targetSum是否和val相等。
4. 只有叶子节点的时间才会去判断val和targetSum的值

class Solution {
    public boolean hasPathSum(TreeNode root, int targetSum) {
        if (root == null) {
            return false;
        }
        return forTarget(root, targetSum);
    }

    public boolean forTarget(TreeNode root, int targetSum) {
        if (root == null) {
            return false;
        }
        if (root.getRight() == null && root.getLeft() == null) {
            return root.getVal() == targetSum;
        }
        return forTarget(root.getLeft(), targetSum - root.getVal())
                || forTarget(root.getRight(), targetSum - root.getVal());
    }

}

结果

最后

以上就是可耐火车最近收集整理的关于二叉树求路径总和的全部内容，更多相关二叉树求路径总和内容请搜索靠谱客的其他文章。