[binary tree] insufficient nodes on the root to leaf path

0x00 subject

Given the root of a binary tree root
Consider it all from root To any leaf route

If through the node node Every possible “ root - leaf ”
Value on the path The sum of the All Small Depending on the given limit
Then this node is called Insufficient nodes , Need to be Delete

Please delete all insufficient nodes , And return the root of the generated binary tree

---

0x01 Ideas

Because to calculate From root to leaf The sum of
So use depth Priority traversal algorithm
node node The condition to be deleted is
sum + node.val < limit
sum Is on the path node Sum of all previous nodes
On the contrary
Every time we pass through a node , Can be updated limit
limit - node.val
When node.val < limit when
It's about to be deleted

---

0x02 solution

Language ：Swift

Tree node ：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
    }
}

solution ：

func sufficientSubset(_ root: TreeNode?, _ limit: Int) -> TreeNode? {
    guard let root = root else { return nil }
    
    let left = root.left
    let right = root.right
    //  To the leaf node 
    if left == nil && right == nil {
        return root.val >= limit ? root : nil
    }
    
    //  Pass through a node , Reduce 
    let res = limit - root.val
    if left != nil {
        root.left = sufficientSubset(left, res)
    }
    if right != nil {
        root.right = sufficientSubset(right, res)
    }
    
    //  After updating the left and right nodes , All is empty 
    //  Description: take the current node as the root , Sum of paths to leaf nodes   Less than  limit
    //  So the current node will also be deleted 
    if root.left == nil && root.right == nil {
        return nil
    }
    return root
}

---

0x03 My work

Welcome to experience one of my works ： Small five strokes 86 edition
Wubi learning is a good helper
App Store Search ~

---