【经典算法】LeetCode112. 路径总和(Java/C/Python3/Go实现含注释说明,Easy)

2024-05-03 02:52
文章标签 java 算法 实现 go 路径 说明 经典 python3 注释 easy 总和 leetcode112

本文主要是介绍【经典算法】LeetCode112. 路径总和(Java/C/Python3/Go实现含注释说明,Easy)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

  • 作者主页： 🔗进朱者赤的博客

  • 精选专栏：🔗经典算法

  • 作者简介：阿里非典型程序员一枚 ，记录在大厂的打怪升级之路。 一起学习Java、大数据、数据结构算法（公众号同名）

  • ❤️觉得文章还不错的话欢迎大家点赞👍➕收藏⭐️➕评论，💬支持博主，记得点个大大的关注，持续更新🤞
    ————————————————-

题目描述

给定一个二叉树和一个目标和，判断该树中是否存在从根节点到叶子节点的路径，
这条路径上所有节点值相加等于目标和。说明: 叶子节点是指没有子节点的节点。

示例 1：
在这里插入图片描述

输入：root = [5,4,8,11,null,13,4,7,2,null,null,null,1], targetSum = 22
输出：true
解释：等于目标和的根节点到叶节点路径如上图所示。
示例 2：

在这里插入图片描述

输入：root = [1,2,3], targetSum = 5
输出：false
解释：树中存在两条根节点到叶子节点的路径：
(1 --> 2): 和为 3
(1 --> 3): 和为 4
不存在 sum = 5 的根节点到叶子节点的路径。
示例 3：

输入：root = [], targetSum = 0
输出：false
解释：由于树是空的，所以不存在根节点到叶子节点的路径。

提示：

树中节点的数目在范围 [0, 5000] 内
-1000 <= Node.val <= 1000
-1000 <= targetSum <= 1000
原题：LeetCode 112

思路及实现

方式一：递归深度优先搜索（DFS）

思路

  • 遍历树的每一个节点。
  • 对于每个节点，判断当前节点到根节点的路径和是否等于目标和，如果等于且当前节点是叶子节点，则返回true。
  • 如果不等于，则继续递归遍历左子树和右子树，并更新目标和为当前目标和减去当前节点的值。

代码实现

Java版本
class TreeNode {int val;TreeNode left;TreeNode right;TreeNode(int x) { val = x; }
}public class Solution {public boolean hasPathSum(TreeNode root, int sum) {if (root == null) {return false;}// 如果是叶子节点，且当前路径和等于目标和if (root.left == null && root.right == null) {return sum == root.val;}// 递归遍历左子树和右子树return hasPathSum(root.left, sum - root.val) || hasPathSum(root.right, sum - root.val);}
}

说明：Java版本使用了递归深度优先搜索的方式，遍历树的每个节点，并不断更新目标和值。

C语言版本
#include <stdbool.h>struct TreeNode {int val;struct TreeNode *left;struct TreeNode *right;
};bool hasPathSum(struct TreeNode* root, int sum){if (root == NULL) {return false;}if (root->left == NULL && root->right == NULL) {return sum == root->val;}return hasPathSum(root->left, sum - root->val) || hasPathSum(root->right, sum - root->val);
}

说明：C语言版本与Java版本类似，也使用了递归深度优先搜索的方式。

Python3版本
class TreeNode:def __init__(self, val=0, left=None, right=None):self.val = valself.left = leftself.right = rightclass Solution:def hasPathSum(self, root: TreeNode, sum: int) -> bool:if not root:return Falseif not root.left and not root.right:return sum == root.valreturn self.hasPathSum(root.left, sum - root.val) or self.hasPathSum(root.right, sum - root.val)

说明：Python3版本也使用了递归深度优先搜索的方式。

Golang版本
package mainimport ("fmt"
)type TreeNode struct {Val   intLeft  *TreeNodeRight *TreeNode
}func hasPathSum(root *TreeNode, sum int) bool {if root == nil {return false}if root.Left == nil && root.Right == nil {return sum == root.Val}return hasPathSum(root.Left, sum-root.Val) || hasPathSum(root.Right, sum-root.Val)
}func main() {// 示例代码，实际使用时需要构建二叉树// ...fmt.Println(hasPathSum(/* root */, /* sum */))
}

说明：Golang版本同样使用了递归深度优先搜索的方式。

复杂度分析

  • 时间复杂度：O(n)，n是二叉树的节点数。每个节点只被访问一次。
  • 空间复杂度：O(h)，h是二叉树的高度。在递归过程中，系统需要为每一层递归调用分配栈空间，因此空间复杂度取决于二叉树的高度。在最坏情况下（树退化为链表），空间复杂度为O(n)。

方式二：迭代深度优先搜索（DFS）

思路

使用栈（Stack）来模拟递归过程，迭代遍历树的每个节点。在遍历过程中，需要额外存储当前路径的路径和（或者称为累积和）。栈中的元素可以是一个自定义的二元组（或结构体），包含当前节点和从根节点到当前节点的路径和。

代码实现

Java版本
import java.util.Stack;class TreeNode {int val;TreeNode left;TreeNode right;TreeNode(int x) { val = x; }
}public class Solution {public boolean hasPathSum(TreeNode root, int sum) {if (root == null) {return false;}Stack<TreeNode> nodeStack = new Stack<>();Stack<Integer> sumStack = new Stack<>();nodeStack.push(root);sumStack.push(root.val);while (!nodeStack.isEmpty()) {TreeNode node = nodeStack.pop();int currentSum = sumStack.pop();if (node.left == null && node.right == null) {if (currentSum == sum) {return true;}}if (node.left != null) {nodeStack.push(node.left);sumStack.push(currentSum + node.left.val);}if (node.right != null) {nodeStack.push(node.right);sumStack.push(currentSum + node.right.val);}}return false;}
}

说明：Java版本使用了两个栈，一个用于存储节点，另一个用于存储从根节点到当前节点的路径和。

C语言版本
#include <stdbool.h>
#include <stdlib.h>typedef struct TreeNode {int val;struct TreeNode *left;struct TreeNode *right;
} TreeNode;typedef struct StackNode {TreeNode *node;int sum;struct StackNode *next;
} StackNode;typedef struct Stack {StackNode *top;
} Stack;StackNode* createStackNode(TreeNode* node, int sum) {StackNode* newNode = (StackNode*)malloc(sizeof(StackNode));newNode->node = node;newNode->sum = sum;newNode->next = NULL;return newNode;
}bool isEmpty(Stack* stack) {return stack->top == NULL;
}void push(Stack* stack, StackNode* node) {node->next = stack->top;stack->top = node;
}StackNode* pop(Stack* stack) {if (isEmpty(stack)) {return NULL;}StackNode* top = stack->top;stack->top = stack->top->next;return top;
}bool hasPathSum(TreeNode* root, int sum) {if (root == NULL) {return false;}Stack stack;stack.top = NULL;push(&stack, createStackNode(root, root->val));while (!isEmpty(&stack)) {StackNode* curr = pop(&stack);TreeNode* node = curr->node;int currentSum = curr->sum;free(curr); // Don't forget to free memory allocated for the StackNodeif (node->left == NULL && node->right == NULL) {if (currentSum == sum) {return true;}}if (node->left != NULL) {push(&stack, createStackNode(node->left, currentSum + node->left->val));}if (node->right != NULL) {push(&stack, createStackNode(node->right, currentSum + node->right->val));}}return false;
}

说明：C语言版本使用了自定义的栈结构来模拟递归过程，同时管理节点和路径和。

C++版本

在上面的代码中，我们定义了一个二叉树节点结构TreeNode，并使用std::stack来实现了一个迭代版本的深度优先搜索（DFS）来检查二叉树中是否存在路径和等于给定值的路径。以下是对代码的一些额外说明和注释，以确保理解每个部分的作用。

#include <iostream>
#include <stack>using namespace std;// 二叉树节点的定义
struct TreeNode {int val;TreeNode *left;TreeNode *right;TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};// 检查是否存在路径和等于给定值的函数
bool hasPathSum(TreeNode* root, int sum) {if (root == nullptr) { // 如果根节点为空，则不存在路径return false;}// 使用栈来存储节点和路径和stack<pair<TreeNode*, int>> stk; // 栈中每个元素是一个pair，包含节点和到该节点的路径和stk.push({root, root->val}); // 初始时将根节点和它的值入栈// 当栈不为空时，继续迭代while (!stk.empty()) {// 弹出栈顶元素pair<TreeNode*, int> curr = stk.top();stk.pop();TreeNode* node = curr.first;int currentSum = curr.second;// 如果当前节点是叶子节点且路径和等于sum，则返回trueif (node->left == nullptr && node->right == nullptr && currentSum == sum) {return true;}// 如果左子节点存在，则将其和路径和的增量入栈if (node->left != nullptr) {stk.push({node->left, currentSum + node->left->val});}// 如果右子节点存在，则将其和路径和的增量入栈if (node->right != nullptr) {stk.push({node->right, currentSum + node->right->val});}}// 如果没有找到满足条件的路径，则返回falsereturn false;
}// 测试代码
int main() {// 构造一个简单的二叉树进行测试// ...（构造二叉树的代码省略）int targetSum = 22;bool result = hasPathSum(root, targetSum);cout << "Does the tree contain a path with sum " << targetSum << "? " << (result ? "Yes" : "No") << endl;// 释放二叉树内存（这里只是示例，实际中可能需要递归释放）// ...（释放二叉树内存的代码省略）return 0;
}

说明
在上面的代码中，我添加了注释来解释每个部分的作用。在hasPathSum函数中，我们使用了一个std::stack来存储节点和路径和的pair。我们首先将根节点和它的值压入栈中，然后进入一个循环，只要栈不为空就继续迭代。在每次迭代中，我们弹出栈顶元素，检查它是否满足路径和等于给定值sum的条件。如果不满足，我们就检查它的左子节点和右子节点是否存在，如果存在，我们就将它们和路径和的增量压入栈中。最后，如果栈为空且没有找到满足条件的路径，我们就返回false。
在main函数中，我们构造了一个二叉树，并调用了hasPathSum函数来检查是否存在路径和等于给定值的路径。然后，我们输出了结果，并注释了释放二叉树内存的部分（这部分在实际应用中需要根据具体的二叉树结构来实现）。

Python3 版本
# Definition for a binary tree node.
class TreeNode:def __init__(self, val=0, left=None, right=None):self.val = valself.left = leftself.right = rightdef hasPathSum(root: TreeNode, sum: int) -> bool:if not root:  # 如果根节点为空，则不存在路径return Falseif not root.left and not root.right:  # 如果是叶子节点，检查路径和是否等于sumreturn root.val == sum# 递归检查左子树和右子树left_has_path = hasPathSum(root.left, sum - root.val)right_has_path = hasPathSum(root.right, sum - root.val)# 只要左子树或右子树中存在满足条件的路径，就返回Truereturn left_has_path or right_has_path
Golang 版本
package mainimport ("fmt"
)// TreeNode represents a binary tree node.
type TreeNode struct {Val   intLeft  *TreeNodeRight *TreeNode
}// hasPathSum checks if there's a path in the binary tree with the given sum.
func hasPathSum(root *TreeNode, sum int) bool {if root == nil { // 如果根节点为空，则不存在路径return false}if root.Left == nil && root.Right == nil { // 如果是叶子节点，检查路径和是否等于sumreturn root.Val == sum}// 递归检查左子树和右子树leftHasPath := hasPathSum(root.Left, sum-root.Val)rightHasPath := hasPathSum(root.Right, sum-root.Val)// 只要左子树或右子树中存在满足条件的路径，就返回truereturn leftHasPath || rightHasPath
}func main() {// ... (构造二叉树并调用函数的代码)// 例如：// root := &TreeNode{Val: 5}// root.Left = &TreeNode{Val: 4}// root.Right = &TreeNode{Val: 8}// ... (继续构造二叉树)// sum := 22// fmt.Println(hasPathSum(root, sum))
}

说明

复杂度分析

  • 时间复杂度：O(N)，其中N是二叉树的节点数。在最坏情况下，我们需要遍历二叉树中的所有节点。
  • 空间复杂度：O(H)，其中H是二叉树的高度。递归调用栈的深度最多为二叉树的高度。在平均情况下，树是平衡的，其高度为O(logN)，但在最坏情况下（例如，树退化为链表），高度为O(N)。

总结

方式优点缺点时间复杂度空间复杂度
递归深度优先搜索（DFS）1. 代码简洁，逻辑清晰 2. 易于理解和实现1. 对于大型树，可能引发栈溢出 2. 递归调用栈占用额外空间O(N)O(H)，其中H为树的高度，最坏情况下为O(N)
迭代深度优先搜索（DFS）1. 避免了栈溢出问题 2. 空间复杂度相对较低1. 需要使用辅助数据结构（如栈） 2. 代码实现相对复杂O(N)O(N) 或 O(H)，取决于使用的辅助数据结构

相似题目

以下是几个与“检查二叉树中是否存在路径和等于给定值”相似的题目，以及它们的难度和链接：

相似题目难度链接
leetcode 112 路径总和简单力扣-112
leetcode 113 路径总和 II中等力扣-113
leetcode 437 路径总和 III中等力扣-437
leetcode 129 求根到叶子节点数字之和中等力扣-129
leetcode 543 二叉树的直径简单力扣-543

注意：以上链接均指向力扣（LeetCode）中国区的题目页面。如果需要访问国际版，可以将链接中的 “leetcode-cn.com” 替换为 “leetcode.com”。

欢迎一键三连(关注+点赞+收藏)，技术的路上一起加油！！！代码改变世界

  • 关于我：阿里非典型程序员一枚 ，记录在大厂的打怪升级之路。 一起学习Java、大数据、数据结构算法（公众号同名），回复暗号，更能获取学习秘籍和书籍等

  • —⬇️欢迎关注下面的公众号：进朱者赤，认识不一样的技术人。⬇️—

这篇关于【经典算法】LeetCode112. 路径总和(Java/C/Python3/Go实现含注释说明,Easy)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/955687。

相关文章

JVM 的类初始化机制

JVM 的类初始化机制

前言 当你在 Java 程序中new对象时，有没有考虑过 JVM 是如何把静态的字节码（byte code）转化为运行时对象的呢，这个问题看似简单，但清楚的同学相信也不会太多，这篇文章首先介绍 JVM 类初始化的机制，然后给出几个易出错的实例来分析，帮助大家更好理解这个知识点。 JVM 将字节码转化为运行时对象分为三个阶段，分别是：loading 、Linking、initialization
阅读更多...
Spring Security 基于表达式的权限控制

Spring Security 基于表达式的权限控制

前言 spring security 3.0已经可以使用spring el表达式来控制授权，允许在表达式中使用复杂的布尔逻辑来控制访问的权限。 常见的表达式 Spring Security可用表达式对象的基类是SecurityExpressionRoot。 表达式描述hasRole([role])用户拥有制定的角色时返回true （Spring security默认会带有ROLE_前缀）,去
阅读更多...
浅析Spring Security认证过程

浅析Spring Security认证过程

类图 为了方便理解Spring Security认证流程，特意画了如下的类图，包含相关的核心认证类 概述 核心验证器 AuthenticationManager 该对象提供了认证方法的入口，接收一个Authentiaton对象作为参数; public interface AuthenticationManager {Authentication authenticate(Authenti
阅读更多...
Spring Security--Architecture Overview

Spring Security--Architecture Overview

1 核心组件 这一节主要介绍一些在Spring Security中常见且核心的Java类，它们之间的依赖，构建起了整个框架。想要理解整个架构，最起码得对这些类眼熟。 1.1 SecurityContextHolder SecurityContextHolder用于存储安全上下文（security context）的信息。当前操作的用户是谁，该用户是否已经被认证，他拥有哪些角色权限…这些都被保
阅读更多...
Spring Security基于数据库验证流程详解

Spring Security基于数据库验证流程详解

Spring Security 校验流程图 相关解释说明（认真看哦） AbstractAuthenticationProcessingFilter 抽象类 /*** 调用 #requiresAuthentication(HttpServletRequest, HttpServletResponse) 决定是否需要进行验证操作。* 如果需要验证，则会调用 #attemptAuthentica
阅读更多...
Spring Security 从入门到进阶系列教程

Spring Security 从入门到进阶系列教程

Spring Security 入门系列 《保护 Web 应用的安全》 《Spring-Security-入门（一）：登录与退出》 《Spring-Security-入门（二）：基于数据库验证》 《Spring-Security-入门（三）：密码加密》 《Spring-Security-入门（四）：自定义-Filter》 《Spring-Security-入门（五）：在 Sprin
阅读更多...
Java架构师知识体认识

Java架构师知识体认识

源码分析 常用设计模式 Proxy代理模式Factory工厂模式Singleton单例模式Delegate委派模式Strategy策略模式Prototype原型模式Template模板模式 Spring5 beans 接口实例化代理Bean操作 Context Ioc容器设计原理及高级特性Aop设计原理Factorybean与Beanfactory Transaction 声明式事物
阅读更多...
不懂推荐算法也能设计推荐系统

不懂推荐算法也能设计推荐系统

本文以商业化应用推荐为例，告诉我们不懂推荐算法的产品，也能从产品侧出发， 设计出一款不错的推荐系统。 相信很多新手产品，看到算法二字，多是懵圈的。 什么排序算法、最短路径等都是相对传统的算法（注：传统是指科班出身的产品都会接触过）。但对于推荐算法，多数产品对着网上搜到的资源，都会无从下手。特别当某些推荐算法 和 “AI”扯上关系后，更是加大了理解的难度。 但，不了解推荐算法，就无法做推荐系
阅读更多...
Zookeeper安装和配置说明

Zookeeper安装和配置说明

一、Zookeeper的搭建方式 Zookeeper安装方式有三种，单机模式和集群模式以及伪集群模式。 ■ 单机模式：Zookeeper只运行在一台服务器上，适合测试环境； ■ 伪集群模式：就是在一台物理机上运行多个Zookeeper 实例； ■ 集群模式：Zookeeper运行于一个集群上，适合生产环境，这个计算机集群被称为一个“集合体”（ensemble） Zookeeper通过复制来实现
阅读更多...
Java进阶13讲__第12讲_1/2

Java进阶13讲__第12讲_1/2

多线程、线程池 1.  线程概念 1.1  什么是线程 1.2  线程的好处 2.   创建线程的三种方式 注意事项 2.1  继承Thread类 2.1.1 认识  2.1.2  编码实现  package cn.hdc.oop10.Thread;import org.slf4j.Logger;import org.slf4j.LoggerFactory
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2