當前位置:網站首頁>【二叉樹】二叉樹路徑總和 II

【二叉樹】二叉樹路徑總和 II

2022-01-27 18:16:56 豪冷啊

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 搜索即可
請添加圖片描述


版權聲明
本文為[豪冷啊]所創,轉載請帶上原文鏈接,感謝
https://cht.chowdera.com/2022/01/202201271816559350.html

隨機推薦