//删除二叉树中的所有叶子节点
void DeleteLev(BiTree T,BiTree f,bool flag){
    if(T){//T is not NULL
        if(T->l){
            DeleteLev(T->l,T,true);
        }
        if(T->r){
            DeleteLev(T->r,T,false);
        }else{//T is a level node
            free(T);
            if(f){// T is not root
                if(flag)f->l = NULL;
                else f->r = NULL;
            }
            
        }
    }
}

void main(){
    Init(T);
    DeleteLev(T,NULL,true);
}

#include<iostream>
#include<cstdlib>
using namespace std;
template<class T>
class BinaryTreeNode{
public:
    T data;
    BinaryTreeNode<T> *leftchild;
    BinaryTreeNode<T> *rightchild;
    BinaryTreeNode(T data = 0){
        this->data = data;
        this->leftchild = rightchild = NULL;
    }
};

template<class T>
class BinaryTree{
private:
    BinaryTreeNode<T> *root;
public:
    BinaryTree(){
        this->root = NULL;
    }
    void visit(BinaryTreeNode<T> *p){
        cout << p->data << "   ";
    }
    BinaryTreeNode<T>* Create(BinaryTreeNode<T> *root);                     //创建二叉树
    void preOrder(BinaryTreeNode<T> *root);                                 //先序遍历二叉树
    void exchange(BinaryTreeNode<T> *root);                                 //交换左右子树
    void deletelea(BinaryTreeNode<T> *root,BinaryTreeNode<T> *pre);         //删除叶子结点
};

template<class T>
BinaryTreeNode<T>* BinaryTree<T> :: Create(BinaryTreeNode<T> *root){
    char x;
    cin >> x;
    if(x == '0')
        return NULL;
    else{
        root = new BinaryTreeNode<T>(x);
        root->leftchild = Create(root->leftchild);
        root->rightchild = Create(root->rightchild);
        return root;
    }
}
template<class T>
void BinaryTree<T> :: preOrder(BinaryTreeNode<T> *root){
    if(root != NULL){
        visit(root);
        preOrder(root->leftchild);
        preOrder(root->rightchild);
    }
}
template<class T>
void BinaryTree<T> :: exchange(BinaryTreeNode<T> *root){
    BinaryTreeNode<T> *temp;
    if(root != NULL){
        temp = root->leftchild;
        root->leftchild = root->rightchild;
        root->rightchild = temp;
        exchange(root->leftchild);
        exchange(root->rightchild);
    }
}
template<class T>
void BinaryTree<T> :: deletelea(BinaryTreeNode<T> *root,BinaryTreeNode<T> *pre){
    if(root!= NULL){
        if(root->leftchild == NULL&&root->rightchild == NULL){
            if(pre != NULL){
                if(root == pre->leftchild)
                    pre->leftchild = NULL;
                if(root == pre->rightchild)
                    pre->rightchild = NULL;
            free(root);
            }
        }
        else{
            pre = root;
            deletelea(root->leftchild,pre);
            deletelea(root->rightchild,pre);
        }

    }
}
int main(){
    BinaryTreeNode<char> *root;
    BinaryTreeNode<char> *pre = NULL;
    BinaryTree<char> *t;
    root = t->Create(root);
    t->preOrder(root);
    /*cout << endl << "交换后的二叉树先序序列为：" << endl;
    t->exchange(root);
    t->preOrder(root);*/
    cout << endl << "删除叶子结点后的二叉树先序序列为：" << endl;
    t->deletelea(root,pre);
    t->preOrder(root);
return 0;
}


 

题目描述：

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

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

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

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

输出：[1,null,3,null,4]

解释：

上面左边的图中，绿色节点为叶子节点，且它们的值与 target 相同（同为 2 ），它们会被删除，得到中间的图。

有一个新的节点变成了叶子节点且它的值与 target 相同，所以将再次进行删除，从而得到最右边的图。
示例 2：

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

输出：[1,3,null,null,2]
示例 3：

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

输出：[1]

解释：每一步都删除一个绿色的叶子节点（值为 2）。
示例 4：

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

输出：[]
示例 5：

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

输出：[1,2,3]
提示：

1 <= target <= 1000

每一棵树最多有 3000 个节点。

每一个节点值的范围是 [1, 1000] 。
方法1：

主要思路：解题链接汇总

（1）后序遍历；

（2）为了确定当前结点的前置结点，使用辅助变量进行存储；
/**
 * 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* post_order(TreeNode*root,TreeNode* pre,const int& target){
        if(root==nullptr){//空结点
            return nullptr;
        }
        
        post_order(root->left,root,target);
        post_order(root->right,root,target);

        if(root->left==nullptr&&root->right==nullptr&&root->val==target){
            if(pre==nullptr){//删除根节点
                return nullptr;
            }
            if(pre->left==root){
                pre->left=nullptr;
            }
            else{
                pre->right=nullptr;
            }
            return pre;//叶子结点已经被删除
        }
        return root;
    }
    TreeNode* removeLeafNodes(TreeNode* root, int target) {
        TreeNode* pre=nullptr;//辅助结点，存储前置结点
        return post_order(root,pre,target);
    }
};

方法2：

主要思路：

（1）去掉辅助前置结点；
/**
 * 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==nullptr){
            return nullptr;
        }
        
        root->left=removeLeafNodes(root->left,target);
        root->right=removeLeafNodes(root->right,target);

        if(root->left==nullptr&&root->right==nullptr&&root->val==target){
            return nullptr;
        }
        return root;
    }
};

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

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

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

 

示例 1：

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

输出：[1,null,3,null,4]

解释：

上面左边的图中，绿色节点为叶子节点，且它们的值与 target 相同（同为 2 ），它们会被删除，得到中间的图。

有一个新的节点变成了叶子节点且它的值与 target 相同，所以将再次进行删除，从而得到最右边的图。

示例 2：

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

输出：[1,3,null,null,2]

示例 3：

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

输出：[1]

解释：每一步都删除一个绿色的叶子节点（值为 2）。

示例 4：

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

输出：[]

示例 5：

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

输出：[1,2,3]

 

提示：

1 <= target <= 1000

每一棵树最多有 3000 个节点。

每一个节点值的范围是 [1, 1000] 。

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @param {number} target
 * @return {TreeNode}
 */
var removeLeafNodes = function(root, target) {
    if(!root) return null;
    root.left = removeLeafNodes(root.left, target);
    root.right = removeLeafNodes(root.right, target);
    if(root.left === null && root.right === null && root.val === target) {
        return null;
    }
    return root;
};