1080.根到叶路径上的不足节点

链接：1080.根到叶路径上的不足节点
难度：Medium
标签：树、深度优先搜索、二叉树
简介：给你二叉树的根节点 root 和一个整数 limit ，请你同时删除树中所有 不足节点 ，并返回最终二叉树的根节点。

题解 1 - python

• 编辑时间：2023-05-22
• 执行用时：84ms
• 内存消耗：17.9MB
• 编程语言：python
• 解法介绍：同上。

def dfs(node: Optional[TreeNode], limit: int, sum: int):
    if node == None:
        return True
    sum += node.val
    l, r = dfs(node.left, limit, sum), dfs(node.right, limit, sum)
    if (not node.left and not node.right and sum < limit) or (not node.left and not r) or (not node.right and not l) or (not l and not r):
        return False
    if not l:
        node.left = None
    if not r:
        node.right = None
    return True

class Solution:
    def sufficientSubset(self, root: Optional[TreeNode], limit: int) -> Optional[TreeNode]:
        return root if dfs(root, limit, 0) else None

题解 2 - rust

• 编辑时间：2023-05-22
• 执行用时：8ms
• 内存消耗：2.5MB
• 编程语言：rust
• 解法介绍：同上。

use std::cell::RefCell;
use std::rc::Rc;
fn dfs(node: &mut Option<Rc<RefCell<TreeNode>>>, limit: i32, mut sum: i32) -> bool {
    match node {
        None => true,
        Some(ref node) => {
            let mut nodeRef = node.as_ref().borrow_mut();
            sum += nodeRef.val;
            let l = dfs(&mut nodeRef.left, limit, sum);
            let r = dfs(&mut nodeRef.right, limit, sum);
            if nodeRef.left.is_none() && nodeRef.right.is_none() && sum < limit
                || nodeRef.left.is_none() && !r
                || nodeRef.right.is_none() && !l
                || !l && !r
            {
                false
            } else {
                if !l {
                    nodeRef.left = None;
                }
                if !r {
                    nodeRef.right = None;
                }
                true
            }
        }
    }
}
impl Solution {
    pub fn sufficient_subset(
        mut root: Option<Rc<RefCell<TreeNode>>>,
        limit: i32,
    ) -> Option<Rc<RefCell<TreeNode>>> {
        if dfs(&mut root, limit, 0) {
            root
        } else {
            None
        }
    }
}

题解 3 - cpp

• 编辑时间：2023-05-22
• 执行用时：40ms
• 内存消耗：32.7MB
• 编程语言：cpp
• 解法介绍：dfs判断下一层节点是否满足。

class Solution {
public:
    TreeNode* sufficientSubset(TreeNode* root, int limit) {
        return dfs(root, limit, 0) ? root : nullptr;
    }
    bool dfs(TreeNode *node, int limit, int sum) {
        if (!node) return true;
        sum += node->val;
        auto l = dfs(node->left, limit, sum), r = dfs(node->right, limit, sum);
        if (!node->left && !node->right && sum < limit ||
            !node->left && !r ||
            !node->right && !l ||
            !l && !r) return false;
        if (!l) node->left = nullptr;
        if (!r) node->right = nullptr;
        return true;
    }
};