二叉树题目:路径总和 III

这篇具有很好参考价值的文章主要介绍了二叉树题目:路径总和 III。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

题目

标题和出处

标题:路径总和 III

出处:437. 路径总和 III

难度

5 级

题目描述

要求

给你二叉树的根结点 root \texttt{root} root 和一个表示目标和的整数 targetSum \texttt{targetSum} targetSum,返回结点值总和等于目标和 targetSum \texttt{targetSum} targetSum 的路径的数目。

路径不需要从根结点开始,也不需要在叶结点结束,但是路径方向必须是向下的(只能从父结点到子结点)。

示例

示例 1:

二叉树题目:路径总和 III,数据结构和算法,# 树,树,二叉树

输入: root   =   [10,5,-3,3,2,null,11,3,-2,null,1],   targetSum   =   8 \texttt{root = [10,5,-3,3,2,null,11,3,-2,null,1], targetSum = 8} root = [10,5,-3,3,2,null,11,3,-2,null,1], targetSum = 8
输出: 3 \texttt{3} 3
解释:和等于 8 \texttt{8} 8 的路径如图所示。

示例 2:

输入: root   =   [5,4,8,11,null,13,4,7,2,null,null,5,1],   targetSum   =   22 \texttt{root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22} root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22
输出: 3 \texttt{3} 3

数据范围

  • 树中结点数目在范围 [0,   1000] \texttt{[0, 1000]} [0, 1000]
  • -10 9 ≤ Node.val ≤ 10 9 \texttt{-10}^\texttt{9} \le \texttt{Node.val} \le \texttt{10}^\texttt{9} -109Node.val109
  • -1000 ≤ targetSum ≤ 1000 \texttt{-1000} \le \texttt{targetSum} \le \texttt{1000} -1000targetSum1000

解法一

思路和算法

定义路径的开始结点是路径中的层数最小(即和根结点距离最小)的结点,结束结点是路径中的层数最大(即和根结点距离最大)的结点。

如果二叉树为空,则不存在结点值总和等于目标和的路径,返回 0 0 0

当二叉树不为空时,遍历二叉树中的每个结点,分别将每个结点作为开始结点,寻找所有结点值总和等于目标和的路径。寻找路径的做法是,在开始结点为根结点的子树中深度优先搜索,假设开始结点值为 val \textit{val} val,则对于开始结点的每个非空子树,子树中的每一条结点值总和等于 targetSum − val \textit{targetSum} - \textit{val} targetSumval 的路径都对应从开始结点出发的一条结点值总和等于 targetSum \textit{targetSum} targetSum 的路径。

由于计算非空子树中的结点值总和等于特定值的路径数目可以使用同样的方法,因此计算路径数目的过程是一个递归的过程。递归的终止条件是二叉树为空,此时路径数目是 0 0 0。对于其余情况,执行如下操作。

  1. 如果根结点值等于目标和,则以根结点为结束结点的路径为结点值总和等于目标和的路径,将路径数目加 1 1 1;如果根结点值不等于目标和,则路径数目不变。

  2. 对左子树和右子树递归地计算路径数目。

代码

class Solution {
    public int pathSum(TreeNode root, int targetSum) {
        if (root == null) {
            return 0;
        }
        int count = countPaths(root, targetSum);
        count += pathSum(root.left, targetSum);
        count += pathSum(root.right, targetSum);
        return count;
    }

    public int countPaths(TreeNode node, long targetSum) {
        if (node == null) {
            return 0;
        }
        int count = 0;
        if (node.val == targetSum) {
            count++;
        }
        count += countPaths(node.left, targetSum - node.val);
        count += countPaths(node.right, targetSum - node.val);
        return count;
    }
}

复杂度分析

  • 时间复杂度: O ( n 2 ) O(n^2) O(n2),其中 n n n 是二叉树的结点数。需要对每个结点计算路径数目,每个结点需要 O ( n ) O(n) O(n) 的时间计算路径数目,因此总时间复杂度是 O ( n 2 ) O(n^2) O(n2)

  • 空间复杂度: O ( n ) O(n) O(n),其中 n n n 是二叉树的结点数。空间复杂度主要是递归调用的栈空间,取决于二叉树的高度,最坏情况下二叉树的高度是 O ( n ) O(n) O(n)

解法二

思路和算法

解法一存在重复计算,因此时间复杂度较高。如果可以存储已经计算过的结果,则可以避免重复计算,降低时间复杂度。

假设从根结点到结点 node 1 \textit{node}_1 node1 的路径上的结点值总和为 sum 1 \textit{sum}_1 sum1,在同一条路径上存在不同于结点 node 1 \textit{node}_1 node1 的结点 node 2 \textit{node}_2 node2,从根结点到结点 node 2 \textit{node}_2 node2 的路径上的结点值总和为 sum 2 \textit{sum}_2 sum2,则该路径上从结点 node 2 \textit{node}_2 node2 的子结点到结点 node 1 \textit{node}_1 node1 的子路径(注意子路径包含 node 1 \textit{node}_1 node1,不包含结点 node 2 \textit{node}_2 node2)上的结点值总和为 sum 1 − sum 2 \textit{sum}_1 - \textit{sum}_2 sum1sum2。如果 sum 1 − sum 2 = targetSum \textit{sum}_1 - \textit{sum}_2 = \textit{targetSum} sum1sum2=targetSum,则找到一条结点值总和等于 targetSum \textit{targetSum} targetSum 的路径。

基于上述分析,可以记录从根结点出发的路径中的每个结点值总和的出现次数,达到优化时间复杂度的目的。以下将从根结点出发的路径中的每个结点值总和称为「根路径和」。

从根结点开始深度优先搜索,使用哈希表记录每个根路径和的出现次数。对于每一条从根结点出发的路径,按照层数递增的顺序依次访问每个结点,访问每个结点时更新当前结点的根路径和,并在哈希表中将当前结点的根路径和的出现次数加 1 1 1。对于访问到的每个结点,如果当前结点的根路径和为 sum \textit{sum} sum,则从哈希表中得到根路径和 sum − targetSum \textit{sum} - \textit{targetSum} sumtargetSum 的出现次数,该出现次数即为以当前结点为结束结点的结点值总和等于 targetSum \textit{targetSum} targetSum 的路径数目。在访问当前结点之后,继续访问当前结点的非空结点。

实现方面有两点需要注意。

  • 由于结点值总和等于 targetSum \textit{targetSum} targetSum 的路径可能从根结点出发,因此需要预处理空路径,空路径的结点值总和等于 0 0 0,在搜索之前将根路径和 0 0 0 出现 1 1 1 次存入哈希表。

  • 深度优先搜索的过程中,当访问完一个子树并退出该子树时,需要撤销对根路径和以及哈希表的更新,避免当前子树的根路径和信息对其他子树的结果造成影响。

代码

class Solution {
    Map<Long, Integer> sumCountMap = new HashMap<Long, Integer>();

    public int pathSum(TreeNode root, int targetSum) {
        if (root == null) {
            return 0;
        }
        sumCountMap.put(0L, 1);
        return getCounts(root, root.val, targetSum);
    }

    public int getCounts(TreeNode node, long sum, int targetSum) {
        int count = sumCountMap.getOrDefault(sum - targetSum, 0);
        sumCountMap.put(sum, sumCountMap.getOrDefault(sum, 0) + 1);
        TreeNode left = node.left, right = node.right;
        if (left != null) {
            count += getCounts(left, sum + left.val, targetSum);
        }
        if (right != null) {
            count += getCounts(right, sum + right.val, targetSum);
        }
        sumCountMap.put(sum, sumCountMap.get(sum) - 1);
        return count;
    }
}

复杂度分析

  • 时间复杂度: O ( n ) O(n) O(n),其中 n n n 是二叉树的结点数。每个结点都被访问一次。

  • 空间复杂度: O ( n ) O(n) O(n),其中 n n n 是二叉树的结点数。空间复杂度主要是递归调用的栈空间以及哈希表空间,取决于二叉树的高度,最坏情况下二叉树的高度是 O ( n ) O(n) O(n)文章来源地址https://www.toymoban.com/news/detail-716511.html

到了这里,关于二叉树题目:路径总和 III的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【算法与数据结构】112、LeetCode路径总和

    所有的LeetCode题解索引,可以看这篇文章——【算法和数据结构】LeetCode题解。    思路分析 :本题通过计算根节点到叶子节点路径上节点的值之和,然后再对比目标值。利用文章【算法和数据结构】257、LeetCode二叉树的所有路径中的递归算法。 这里要注意,默认路径之和是

    2024年02月11日
    浏览(53)
  • 【数据结构-二叉树】二叉树

    💝💝💝欢迎来到我的博客,很高兴能够在这里和您见面!希望您在这里可以感受到一份轻松愉快的氛围,不仅可以获得有趣的内容和知识,也可以畅所欲言、分享您的想法和见解。 推荐:kuan 的首页,持续学习,不断总结,共同进步,活到老学到老 导航 檀越剑指大厂系列:全面总

    2024年02月07日
    浏览(48)
  • 数据结构:搜索二叉树 | 平衡二叉树

    博客写的代码都放在这里:gitee仓库链接 1.二叉搜索树 1.1.基本概念 二叉搜索树又称二叉排序树, 可以为空,如果不为空具有以下性质的二叉树 : 若它的左子树不为空,则左子树上所有节点的值都小于根节点的值 若它的右子树不为空,则右子树上所有节点的值都大于根节点的

    2024年01月23日
    浏览(58)
  • 【数据结构和算法】--- 二叉树(3)--二叉树链式结构的实现(1)

    在学习二叉树的基本操作前,需先要创建一棵二叉树,然后才能学习其相关的基本操作。由于现在大家对二叉树结构掌握还不够深入,且为了方便后面的介绍,此处手动快速创建一棵简单的二叉树,快速进入二叉树操作学习,等二叉树结构了解的差不多时,我们反过头再来研

    2024年01月25日
    浏览(63)
  • 剑指 Offer 34. 二叉树中和为某一值的路径 / LeetCode 113. 路径总和 II(深度优先搜索)

    链接:剑指 Offer 34. 二叉树中和为某一值的路径;LeetCode 113. 路径总和 II 难度:中等 给你二叉树的根节点 root 和一个整数目标和 targetSum ,找出所有 从根节点到叶子节点 路径总和等于给定目标和的路径。 叶子节点 是指没有子节点的节点。 示例 1: 输入:root = [5,4,8,11,null,1

    2024年02月03日
    浏览(42)
  • 【数据结构】二叉树——链式结构

    目录  一、前置声明 二、二叉树的遍历 2.1 前序、中序以及后序遍历 2.2 层序遍历 三、节点个数以及高度 3.1 节点个数 3.2 叶子节点个数 3.3 第k层节点个数 3.4 二叉树的高度/深度 3.5 查找值为x的节点 四、二叉树的创建和销毁 4.1 构建二叉树 4.2 二叉树销毁 4.3 判断二叉树

    2024年02月16日
    浏览(47)
  • 【数据结构】二叉树——顺序结构

    由于每个节点都 只有一个父节点 ,所以我们可通过双亲来表示一棵树。具体方式通过 数组的形式 实现。 根节点的下标为0 按照层序从上到下排序 每层从左向右递增 表示形式: 二维数组 数据的列标为0 ,只需确定行标,即可锁定位置 根节点的父节点下标为 -1 列标为1存父节

    2024年02月02日
    浏览(56)
  • 数据结构-二叉树-二叉树左右孩子交换(递归)

     注:本文采用队列和递归的算法进行创建和层次遍历。同时不能采用BFS和DFS,因为需要把当前根节点的左孩、右孩勾链并输入才能递归下一个根节点; 队列用于存储此时应该递归的根节点; 格式:每一行尾不能有空格; Description 根据输入利用二叉链表创建二叉树,并将所

    2024年02月04日
    浏览(50)
  • 第18天-代码随想录刷题训练-第六章● 513.找树左下角的值 ● 112. 路径总和 113.路径总和ii ● 106.从中序与后序遍历序列构造二叉树 105.从前序与中序遍历序列构造二叉树

    - LeetCode链接 给定一个二叉树的 根节点 root,请找出该二叉树的 最底层 最左边 节点的值。 假设二叉树中至少有一个节点。 遍历顺序,因为本题要求的是 最后一层最左边的节点,因此只要遍历顺序 左节点在右节点前就行,因此 任何遍历顺序都可以 本题中的中节点 不需要处

    2024年02月04日
    浏览(51)
  • 【数据结构】二叉树链式结构

    🚀write in front🚀 📜所属专栏:初阶数据结构 🛰️博客主页:睿睿的博客主页 🛰️代码仓库:🎉VS2022_C语言仓库 🎡您的点赞、关注、收藏、评论,是对我最大的激励和支持!!! 关注我,关注我,关注我 , 你们将会看到更多的优质内容!!   在之前的二叉树的顺序结

    2024年02月03日
    浏览(41)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包