【二叉樹】路徑總和 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()
}      

小程式應用