1. 题目

给定一个二叉树的根节点root ，和一个整数targetSum ，求该二叉树里节点值之和等于targetSum的 路径的数目

路径不需要从根节点开始，也不需要在叶子节点结束，但是路径方向必须是向下的（只能从父节点到子节点）

示例1：

  1. 输入：root = [10, 5, -3, 3, 2, nil, 11, 3, -2, nil, 1], targetSum = 8
  2. 输出：3

image.png

  • 路径之和等于8，共计3条
  2. class Solution {
  3.     func pathSum(_ root: TreeNode?, _ sum: Int) -> Int {
  5.         //空直接返回
  6.         guard let root = root else {
  7.             return 0
  8.         }
  10.         //定义一个函数，计算输入的路径里是否存在满足条件的路径
  11.         //它的工作原理是将输入数组的最后一个元素(对应二叉树新遍历到的节点的值)依次和其它元素(对应二叉树已经探访过的节点)相加
  12.         //如果和为指定值，则count+1.计算必须包含新探访到的节点的原因是为了避免求重
  13.         func roots(in arr:[Int], equal sum:Int) -> Int {
  14.             var count = 0
  15.             var temp = arr[arr.count - 1]
  17.             if temp == sum {
  18.                 count += 1
  19.             }
  21.             for element in arr.dropLast().reversed() {
  22.                 temp += element
  23.                 if temp == sum {
  24.                     count += 1
  25.                 }
  26.             }
  27.             return count
  28.         }
  30.         //初始化一个栈用来存储二叉树 当前指向的节点 和 已经探索过的节点的信息
  31.         var stack:[(TreeNode,[Int])] = [(root, [root.val])]
  32.         //定义返回值
  33.         var result = 0
  35.         //遍历二叉树，不断由根向叶探索所有节点。每探索到一个新节点，就把这个节点和该节点的值加入到元组中
  36.         while let node = stack.last?.0, let valueSum = stack.last?.1 {
  37.             stack.removeLast()
  39.             //每探索到一个新节点都去探查下有没有包含这个节点的满足条件的路径
  40.             result += roots(in: valueSum, equal: sum)
  42.             if node.left != nil {
  43.                 stack.append((node.left!, valueSum + [node.left!.val]))
  44.             }
  46.             if node.right != nil {
  47.                 stack.append((node.right!, valueSum + [node.right!.val]))
  48.             }
  49.         }
  51.         return result
  52.     }
  53. }