1325. Delete Leaves With a Given Value

桃扇骨 2024-04-08 09:28 63阅读 0赞

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:**

![8c48e64e9440f94b92a238e8873fc27a.png][]

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:**

![bfed2e2a797fcd5cceaf924e100024ed.png][]

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

**Example 3:**

![0fcab8a61357cf21633ea1e8ec11f4a3.png][]

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`

题目：给定一个二叉树，将与给定target值相等的叶结点删除。注意，删除之后其父结点可能变为叶结点。

思路：一看就是递归，从下网上删就完了。代码：

/**
     * Definition for a binary tree node.
     * struct TreeNode {
     *     int val;
     *     TreeNode *left;
     *     TreeNode *right;
     *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
     *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
     *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
     * };
     */
    class Solution {
    public:
        TreeNode* removeLeafNodes(TreeNode* root, int target) {
            if(!root) return NULL;
            root->left = removeLeafNodes(root->left, target);
            root->right = removeLeafNodes(root->right, target);
            if(!root->left && !root->right && root->val == target)
                return NULL;
            return root;
        }
    };

[8c48e64e9440f94b92a238e8873fc27a.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/08/0d60f411acc24b49ac8c21d598151ddd.png
[bfed2e2a797fcd5cceaf924e100024ed.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/08/5bbfa3d5d9334afeaa1f54f34ce896c7.png
[0fcab8a61357cf21633ea1e8ec11f4a3.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/08/35c84583a5d846fea6850dbf7b615f51.png