当前位置：首页 > article >正文

【数据结构和算法实践-树-LeetCode112-路径总和】

article 2024/9/22 22:37:17

数据结构和算法实践-树-LeetCode112-路径总和

- 题目
- My Thought
- 代码示例
- - JAVA-8

题目

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

My Thought

题目限定的条件为是否存在到叶子节点的路径总和与目标相等：
一、到叶子节点的时候，是不是会等于给定的sum
二、如果有一条相等就算是通过，所以要设置一个全局变量
三、处理过程递归就是当前值、左节点、右节点
然后再进行递归，递归要注意两个方面：
一、自我调用
二、终止条件：即函数边界
注意点：树、递归

代码示例

JAVA-8

    /**
     * 一、到叶子节点的时候，是不是会等于给定的sum
     * 二、如果有一条相等就算是通过，所以要设置一个全局变量
     * 三、处理过程递归就是当前值、左节点、右节点
     */
    public static boolean isSum = false;

    public static boolean hasPathSum(TreeNode root, int sum) {
        if (root == null) {
            return false;
        }
        isSum = false;
        process(root, 0, sum);
        return isSum;
    }

    private static void process(TreeNode node, int preSum, int targetSum) {
        if (node == null) {
            return;
        }
        if (node.left == null && node.right == null) {
            if (node.val + preSum == targetSum) {
                isSum = true;
            }
            return;
        }
        preSum += node.val;
        process(node.left, preSum, targetSum);
        process(node.right, preSum, targetSum);
    }