【二叉樹】統計二叉樹中好節點的數目

0x00 題目

給你一棵根為 ​

​root​

​​ 的二叉樹

請你傳回二叉樹中​​

​好節點​

​的數目

「好節點」X 定義為：

從根到該節點 ​​

​X​

​​ 所經過的節點中

​​

​沒有​

​​任何節點的值​

​大于​

​ X 的值

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 goodNodes(_ root: TreeNode?) -> Int {
    guard let root = root else { return 0 }
    var res: Int = 0
    
    func dfs(_ root: TreeNode?, _ val: Int) {
        guard let root = root else { return }

        // 是否是好節點
        if root.val >= val { res += 1}
        
        // 計算該條路徑的最大值
        let big = max(root.val, val)
        
        // 遞歸左右節點
        dfs(root.left, big)
        dfs(root.right, big)
    }

    dfs(root, Int.min)
    
    return res
}      

0x03 我的小作品