路径总和-112

Java资料网推荐路径总和-112这篇文章给大家，欢迎收藏Java资料网享受知识的乐趣

题目描述

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

解题思路

我们这题采用任何一种遍历方式都是可以的，这题同样是有回溯的思想，如果不太懂的话可以去看看前面《求二叉树的左右路径》这一题，我们先去遍历左子树，遍历的时候如果节点的左右子树都为空说明我们已经到了叶子节点，此时我们就可以做判断了，看看是不是和我们的targetSum一致，如果不一致则它的父节点会产生回溯去遍历父节点的另一个子树，同样再去看看是否和targetSum是否一致，如果一致就可以直接填写结果，不一致则继续由它们的父节点回溯去判断另一颗子树。

代码实例

class Solution {
    public boolean judge = false;

    public boolean hasPathSum(TreeNode root, int targetSum) {
        List<Integer> list = new ArrayList<>();
        if(root==null){
            return false;
        }else{
            list.add(root.val);
            bianli(root, targetSum, list);
            return judge;
        }

    }

    public void bianli(TreeNode root, int targetSum, List<Integer> list) {
        if (root.left == null && root.right == null) {
            if (sum(list) == targetSum) {
                judge = true;
                return;
            }
        }
        
        if (root.left != null) {
            list.add(root.left.val);
            bianli(root.left, targetSum, list);
            list.remove(list.size() - 1);
        }

        if (root.right != null) {
            list.add(root.right.val);
            bianli(root.right, targetSum, list);
            list.remove(list.size() - 1);

        }

    }

    public int sum(List<Integer> list) {
        int sum = 0;
        for (Integer in : list) {
            sum += in;
        }
        return sum;
    }

}

文章来源:https://www.cnblogs.com/dfj-blog/p/18416256
本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若内容造成侵权/违法违规/事实不符，请联系邮箱：jacktools123@163.com进行投诉反馈，一经查实，立即删除！