力扣0113——路径总和II

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

路径总和II

难度：中等

题目描述

给你二叉树的根节点 root 和一个整数目标和 targetSum ，找出所有 从根节点到叶子节点 路径总和等于给定目标和的路径。

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

示例1

输入： root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22
输出：[[5,4,11,2],[5,8,4,5]]

示例2

输入： root = [1,2,3], targetSum = 5
输出：[]

示例3

输入： root = [1,2], targetSum = 0
输出：[]

题解

和 0112 题的思路一致，都是对targetSum进行减法回溯，不同的是需要记录当前节点的值

想法代码

using System;
using System.Collections.Generic;
using System.Linq;
using System.Runtime.Remoting.Metadata.W3cXsd2001;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(7),right = new TreeNode(2)}},right = new TreeNode{val = 8,left = new TreeNode(13),right = new TreeNode{val = 4,left = new TreeNode(5),right = new TreeNode(1)}}};Solution solution = new Solution();IList<IList<int>> currans = solution.PathSum(root, 22);foreach (var a in currans){foreach (var b in a){Console.Write(b + " ");}Console.WriteLine();}Console.ReadKey();}IList<IList<int>> ans = new List<IList<int>>();IList<int> temp = new List<int>();public IList<IList<int>> PathSum(TreeNode root, int targetSum){BackTrack(root, targetSum);return ans;}public void BackTrack(TreeNode root, int targetSum){if (root == null){return;}temp.Add(root.val);if (root.val == targetSum && root.left == null && root.right == null){ans.Add(new List<int>(temp));}BackTrack(root.left, targetSum - root.val);BackTrack(root.right, targetSum - root.val);temp.RemoveAt(temp.Count - 1);}
}