【二叉树】根到叶路径上的不足节点

0x00 题目

给定一棵二叉树的根 root
考虑它所有从根到任何叶 路径

假如通过节点 node 的每种可能的 “根-叶”
路径上值的总和全都小于给定的 limit
则该节点被称之为不足节点，需要被删除

请你删除所有不足节点，并返回生成的二叉树的根

---

0x01 思路

因为要计算从根到叶的总和
所以使用深度优先的遍历算法
节点 node 被删除的条件是
sum + node.val < limit
sum 为路径上 node 前面所有节点的和
反过来讲
每经过一个节点，可以更新 limit
limit - node.val
当 node.val < limit 时
就要被删除

---

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 sufficientSubset(_ root: TreeNode?, _ limit: Int) -> TreeNode? {
    guard let root = root else { return nil }
    
    let left = root.left
    let right = root.right
    // 到达叶子节点
    if left == nil && right == nil {
        return root.val >= limit ? root : nil
    }
    
    // 经过一个节点，减小
    let res = limit - root.val
    if left != nil {
        root.left = sufficientSubset(left, res)
    }
    if right != nil {
        root.right = sufficientSubset(right, res)
    }
    
    // 更新左右节点后，都为空
    // 说明以当前节点为根，到叶子节点的路径总和 小于 limit
    // 所以当前节点也要被删除
    if root.left == nil && root.right == nil {
        return nil
    }
    return root
}

---

0x03 我的作品

欢迎体验我的作品之一：小五笔 86 版
五笔学习好帮手
App Store 搜索即可~

---