![cover](https://img-blog.csdnimg.cn/direct/83f630732bf34a68b47a3a171b9bb0f1.png)
【经典算法】LeetCode112. 路径总和(Java/C/Python3/Go实现含注释说明,Easy)
方式优点缺点时间复杂度空间复杂度递归深度优先搜索(DFS)1. 代码简洁,逻辑清晰2. 易于理解和实现1. 对于大型树,可能引发栈溢出2. 递归调用栈占用额外空间O(N)O(H),其中H为树的高度,最坏情况下为O(N)迭代深度优先搜索(DFS)1. 避免了栈溢出问题2. 空间复杂度相对较低1. 需要使用辅助数据结构(如栈)2. 代码实现相对复杂O(N)O(N) 或 O(H),取决于使用的辅助数据结
题目描述
给定一个二叉树和一个目标和,判断该树中是否存在从根节点到叶子节点的路径,
这条路径上所有节点值相加等于目标和。
说明: 叶子节点是指没有子节点的节点。
示例 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 = val
self.left = left
self.right = right
class Solution:
def hasPathSum(self, root: TreeNode, sum: int) -> bool:
if not root:
return False
if not root.left and not root.right:
return sum == root.val
return self.hasPathSum(root.left, sum - root.val) or self.hasPathSum(root.right, sum - root.val)
说明:Python3版本也使用了递归深度优先搜索的方式。
Golang版本
package main
import (
"fmt"
)
type TreeNode struct {
Val int
Left *TreeNode
Right *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 StackNode
if (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,则返回true
if (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});
}
}
// 如果没有找到满足条件的路径,则返回false
return 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 = val
self.left = left
self.right = right
def hasPathSum(root: TreeNode, sum: int) -> bool:
if not root: # 如果根节点为空,则不存在路径
return False
if not root.left and not root.right: # 如果是叶子节点,检查路径和是否等于sum
return root.val == sum
# 递归检查左子树和右子树
left_has_path = hasPathSum(root.left, sum - root.val)
right_has_path = hasPathSum(root.right, sum - root.val)
# 只要左子树或右子树中存在满足条件的路径,就返回True
return left_has_path or right_has_path
Golang 版本
package main
import (
"fmt"
)
// TreeNode represents a binary tree node.
type TreeNode struct {
Val int
Left *TreeNode
Right *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 { // 如果是叶子节点,检查路径和是否等于sum
return root.Val == sum
}
// 递归检查左子树和右子树
leftHasPath := hasPathSum(root.Left, sum-root.Val)
rightHasPath := hasPathSum(root.Right, sum-root.Val)
// 只要左子树或右子树中存在满足条件的路径,就返回true
return 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、大数据、数据结构算法(公众号同名),回复暗号,更能获取学习秘籍和书籍等
—⬇️欢迎关注下面的公众号:
进朱者赤
,认识不一样的技术人。⬇️—
更多推荐
所有评论(0)