LeetCode每日一题(1325. Delete Leaves With a Given Value)

Given a binary tree root and an integer target, delete all the leaf nodes with value target.

Note that once you delete a leaf node with value target, if its parent node becomes a leaf node and has the value target, it should also be deleted (you need to continue doing that until you cannot).

Example 1:

Input: root = [1,2,3,2,null,2,4], target = 2
Output: [1,null,3,null,4]

Explanation: Leaf nodes in green with value (target = 2) are removed (Picture in left).
After removing, new nodes become leaf nodes with value (target = 2) (Picture in center).

Example 2:

Input: root = [1,3,3,3,2], target = 3
Output: [1,3,null,null,2]

Example 3:

Input: root = [1,2,null,2,null,2], target = 2
Output: [1]

Explanation: Leaf nodes in green with value (target = 2) are removed at each step.

Constraints:

• The number of nodes in the tree is in the range [1, 3000].
• 1 <= Node.val, target <= 1000

---

送分题， 就不多做赘述了， 如果左右两个子节点返回的都是 null， 且当前节点的 value == target， 则删除当前节点， 返回 null， 否则的话则将已经完成删除操作的左右子节点重新赋值给当前节点的左右子节点。

---

use std::cell::RefCell;
use std::rc::Rc;
impl Solution {
    fn dfs(root: Option<Rc<RefCell<TreeNode>>>, target: i32) -> Option<Rc<RefCell<TreeNode>>> {
        if let Some(node) = root {
            let left = Solution::remove_leaf_nodes(node.borrow_mut().left.take(), target);
            let right = Solution::remove_leaf_nodes(node.borrow_mut().right.take(), target);
            if left.is_none() && right.is_none() && node.borrow().val == target {
                return None;
            }
            node.borrow_mut().left = left;
            node.borrow_mut().right = right;
            return Some(node);
        }
        None
    }
    pub fn remove_leaf_nodes(
        root: Option<Rc<RefCell<TreeNode>>>,
        target: i32,
    ) -> Option<Rc<RefCell<TreeNode>>> {
        Solution::dfs(root, target)
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23