0x00 題目

給你二叉樹的根節點 root
和一個整數目標和 targetSum
找出 所有 從 根節點 到 葉子節點 路徑總和
等於給定 目標和 的路徑

葉子節點 是指沒有子節點的節點

0x01 思路

這道題目跟之前的一道題目類似：二叉樹的所有路徑
只要找出所有路徑即可

本題則加了一個條件：
路徑總和 要與 目標和 相等

找出符合條件的路徑即可

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
    }
}

解法：

func pathSum(_ root: TreeNode?, _ targetSum: Int) -> [[Int]] {
    guard let root = root else { return [] }
    
    // 存放結果
    var res: [[Int]] = []
    // 存放節點值
    var arr: [Int] = []

    func dfs(_ root: TreeNode?, _ target: Int) {
        guard let root = root else { return }
        // 添加一個數
        arr.append(root.val)
        
        // 减小目標
        let val = target - root.val
        
        // 葉子節點
        if root.left == nil && root.right == nil {
            // 符合條件
            if val == 0 { 
                res.append(arr)
            }
            // 删除最後一個數，返回後，添加其他節點值繼續判斷
            arr.removeLast() 
            return
        }

        dfs(root.left, val)
        dfs(root.right, val)
        
        // 删除最後一個數，返回後，添加其他節點值繼續判斷
        arr.removeLast() 
    }

    dfs(root, targetSum)

    return res
}

小筆記

做筆記，一步到比特
App Store 搜索即可