【二叉树】路径总和 III

0x00 题目

给定一个二叉树的根节点 ​

​root​

​​ 和一个整数 ​

​targetSum​

​ 求该二叉树里​

​节点值​

​之和

等于 ​

​targetSum​

​ 的 ​

​路径​

​ 的数目

路径不需要从根节点​

​开始​

​​ 也不需要在叶子节点​

​结束​

​ 但是路径方向必须是​

​向下​

​的（只能从父节点到子节点）

示例如图：

0x01 思路

这道题目跟之前的一道题目类似：​​二叉树路径总和 II​​

方法一：

相当于要从​​

​每个​

​节点出发，都要查找一遍

方法二：

经过每一层时，保存当前节点的​​

​值​

​​ 从当前节点​

​向上​

​往​

​根​

​节点找

看是否存在​

​符合​

​条件的路径

有种​

​“一步一回头”​

​的意思

每往前走一步，就​

​回头​

​计算一下路径

看看是否存在​

​符合​

​条件的路径

0x02 解法

语言：​

​Swift​

​

树节点：​

​TreeNode​

​

public class TreeNode {
    public var val: Int
    public var left: TreeNode?
    public var right: TreeNode?
    public init() { self.val = 0; self.left = nil; self.right = nil; }
    public init(_ val: Int) { self.val = val; self.left = nil; self.right = nil; }
    public init(_ val: Int, _ left: TreeNode?, _ right: TreeNode?) {
        self.val = val
        self.left = left
        self.right = right
    }
}      

解法一：

private var count: Int = 0

func pathSum(_ root: TreeNode?, _ targetSum: Int) -> Int {
    guard let root = root else { return 0 }

    // 从根节点出发
    path(root, targetSum)
    
    // 递归左右节点
    _ = pathSum(root.left, targetSum)
    _ = pathSum(root.right, targetSum)

    return count
}

func path(_ root: TreeNode?, _ sum: Int){
    guard let root = root else { return }

    if root.val == sum {
        count += 1
    }

    // 往下层走，目标值减小
    let val = sum - root.val
    path(root.left, val)
    path(root.right, val)
}      

private var count = 0

func pathSum(_ root: TreeNode?, _ targetSum: Int) -> Int {
    var paths: [Int] = []
    dfs(root, targetSum, &paths)
    return count
}

private func dfs(_ root: TreeNode?, _ sum: Int, _ paths: inout [Int]) {
    guard let root = root else { return }
    // 把当前节点值加入路径
    paths.append(root.val)

    // 回头计算路径和
    var currentSum = 0
    var i = paths.count - 1
    while i >= 0 {
        currentSum += paths[i]
        if (currentSum == sum) {
            count += 1 // 符合条件加 1
        }
        i -= 1
    }
    
    // 递归子节点
    dfs(root.left, sum, &paths)
    dfs(root.right, sum, &paths)
    
    // 把当前节点值移除，往回走，走其他路径
    paths.removeLast()
}      

小程序应用