力扣0112——路径总和

2024-01-29 14:04

文章标签 路径力扣总和 0112

本文主要是介绍力扣0112——路径总和，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

路径总和

难度：简单

题目描述

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

叶子节点 是指没有子节点的节点。

示例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

示例3

输入： root = [], targetSum = 0
输出： false

题解

使用回溯法，因为最终的结果是节点值之和，所以可以使用累减方法进行回溯，当相等的时候可以直接返回true

想法代码

using System;
using System.Collections;
using System.Collections.Generic;public class TreeNode
{public int val;public TreeNode left;public TreeNode right;public TreeNode(int val = 0, TreeNode left = null, TreeNode right = null){this.val = val;this.left = left;this.right = right;}
}public class Solution
{public static void Main(string[] args){TreeNode root = new TreeNode{val = 5,left = new TreeNode{val = 4,left = new TreeNode{val = 11,left = new TreeNode{val = 7},right = new TreeNode{val = 2}}},right = new TreeNode{val = 8,left = new TreeNode(13),right = new TreeNode{val = 4,right = new TreeNode(1)}}};Solution solution = new Solution();bool ans = solution.HasPathSum(root, 22);Console.WriteLine(ans);}public bool HasPathSum(TreeNode root, int targetSum){if (root == null){return false;}if (root.left == null && root.right == null){return targetSum == root.val;}return HasPathSum(root.left,targetSum - root.val) || HasPathSum(root.right,targetSum - root.val);}
}