题目描述

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

注意，一旦删除值为 target 的叶子节点，它的父节点就可能变成叶子节点；如果新叶子节点的值恰好也是 target ，那么这个节点也应该被删除。

也就是说，你需要重复此过程直到不能继续删除。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/delete-leaves-with-a-given-value
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

样例

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

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

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

算法1

(暴力枚举) $O(n^2)$

这道题有个特殊的要求，如果一个结点的儿子结点都被删除，而且他的值也等于target，则也要删除这个结点。思路就是前序遍历，先删除其左右子树中的目标结点，在返回以后如果这个结点是叶子节点（删除之前就是叶子节点或者他的子节点都被删除了），并且值等于target则删除也这个结点。

C++ 代码

class Solution {
public:
    TreeNode* dfs(TreeNode* t, int target){
        if(!t) return NULL;//空树返回null
        t->left = dfs(t->left, target);//在左右子树中删除，并更新两个结点指针。
        t->right = dfs(t->right, target);
        if(!t->left && !t->right && t->val == target) return NULL;//叶子节点并且值为target，删除。
        return t;//没有删除。
    }

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