算法 - 路径和问题（1）问题描述算法描述代码复杂度

63 阅读 0 评论 42 点赞

我是靠谱客的博主欣慰夏天，最近开发中收集的这篇文章主要介绍算法 - 路径和问题（1）问题描述算法描述代码复杂度，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

问题描述

给定一个二叉树、一个数字，判断是否存在一条从根节点
到叶节点的路径上的数字总和等于给定数字。
如：给定如下二叉树，以及数字22，判断是否存在某条路
径满足上述条件
      5
     / 
    4   8
   /   / 
  11  13  4
 /        
7    2      1

算法描述

最直接的方式就是使用递归方法去遍历每一条边，进行求
和计算，查找出满足条件的路径。

代码

public static boolean hasPathSumRecursion(TreeNode root, int sum) {
    if(root == null) {
        return false;
    }
    sum -= root.val;
    if ((root.left == null) && (root.right == null))
        return (sum == 0);
    return hasPathSumRecursion(root.left,sum) || hasPathSumRecursion(root.right,sum);
}

复杂度

时间复杂度：O(N)
空间复杂度：
	完全不平衡二叉树 - O(N)
	平衡二叉树 - O(log(N))

最后

以上就是欣慰夏天为你收集整理的算法 - 路径和问题（1）问题描述算法描述代码复杂度的全部内容，希望文章能够帮你解决算法 - 路径和问题（1）问题描述算法描述代码复杂度所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。

本图文内容来源于网友提供，作为学习参考使用，或来自网络收集整理，版权属于原作者所有。

本文分类：算法
浏览次数：63 次浏览
发布日期：2023-09-25 14:31:09
本文链接：https://www.kaopuke.com/article/k-p-k_14_uzocf0_14__23__6_3.html

算法 - 路径和问题（1）问题描述算法描述代码复杂度

概述

问题描述

算法描述

代码

复杂度

最后

评论列表共有 0 条评论

发表评论取消回复

算法 - 路径和问题（1）问题描述算法描述代码复杂度

概述

问题描述

算法描述

代码

复杂度

最后

相关文章

评论列表共有 0 条评论

发表评论 取消回复

发表评论取消回复