题目描述

给你一棵以 root 为根的二叉树和一个整数 target，请你删除所有值为 target 的 叶子结点。

注意，一旦删除值为 target 的叶子结点，如果它的父结点变成叶子结点且值恰好也是 target，那么这个父结点也应该被删除（你需要重复此过程直到不能继续删除）。

样例

输入：root = [1,2,3,2,null,2,4], target = 2
输出：[1,null,3,null,4]
解释：
上面左边的图中，绿色结点为叶子结点，且它们的值与 target 相同（同为 2），它们会被删除，得到中间的图。
有一个新的结点变成了叶子结点且它的值与 target 相同，所以将再次进行删除，从而得到最右边的图。

输入：root = [1,3,3,3,2], target = 3
输出：[1,3,null,null,2]

输入：root = [1,2,null,2,null,2], target = 2
输出：[1]
解释：每一步都删除一个绿色的叶子结点（值为 2）。

输入：root = [1,1,1], target = 1
输出：[]

输入：root = [1,2,3], target = 1
输出：[1,2,3]

限制

• 1 <= target <= 1000
• 每一棵树最多有 3000 个结点。
• 每一个结点值的范围是 [1, 1000]。

算法

(递归) $O(n)$

1. 通过递归来实现删除。
2. 如果左右子结点都是空，而且自身结点的值为 target，则将自己变为 NULL。
3. 注意，第一种实现的递归函数参数需要使用指针的引用类型。

时间复杂度

• 每个点仅遍历一次，故时间复杂度为 $O(n)$。

空间复杂度

• 需要额外的系统栈空间，故空间复杂度为 $O(n)$。

C++ 代码 1

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    void solve(TreeNode *&r, int target) {
        if (!r) return;

        solve(r -> left, target);
        solve(r -> right, target);

        if (!(r -> left) && !(r -> right) && r -> val == target)
            r = NULL;
    }

    TreeNode* removeLeafNodes(TreeNode* root, int target) {
        solve(root, target);
        return root;
    }
};

C++ 代码 2

• 不需要引用，但需要返回值

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
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;
    }
};