删层子树__牛客网

loveling

层序遍历，遍历时对节点依次进行如下操作：

1.若当前节点上一层应该删除且这一层不用删除，将该节点填入答案。

2.将当前节点左右儿子填入遍历队列。

3.若当前节点下一层需要删除时，断开当前节点左右儿子的连接。

特殊处理：遍历前，将第0层（根节点的上层，在树中不存在）设置为需要删除，在对根节点执行操作1时，若第1层不需要删除，会将根节点填入答案，以免漏掉根节点。

/**
 * struct TreeNode {
 *	int val;
 *	struct TreeNode *left;
 *	struct TreeNode *right;
 *	TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 * };
 */
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param root TreeNode类 
     * @param a int整型vector 
     * @return TreeNode类vector
     */
    vector<TreeNode*> deleteLevel(TreeNode* root, vector<int>& a) {
        // write code here
        vector<TreeNode*> ans;
        unordered_map<int,int> m;
        m[0]=1;
        for(auto num:a)
            m[num]=1;
        queue<pair<TreeNode*, int>> que;
        que.push(make_pair(root, 1));
        while(!que.empty())
        {
            pair<TreeNode*, int> p = que.front();
            que.pop();
            TreeNode* t = p.first;
            int high = p.second;
            if(t==nullptr)
                continue;
            if(m.find(high-1)!=m.end() && m.find(high)==m.end())
                ans.push_back(t);
            que.push(make_pair(t->left, high+1));
            que.push(make_pair(t->right, high+1));
            if(m.find(high+1)!=m.end())
            {
                t->left=nullptr;
                t->right=nullptr;
            }
        }
        return ans;
    }
};

编辑于 2022-06-15 18:13:10 回复(2)

枉做好人

//1.使用HashSet记录要删除的深度，注意要添加第0层，因为根节点也可以看作被删掉上一层的。
//2.使用BFS常规模板,并记录层序深度
//3.hashset.contains(depth) 来判断是否需要加入该层的节点(各个子树的头节点)
//4.处于要删除的层的上一层，因为已经将左右节点入队了，因此只需要将左右指针置空jiu'ke'yu  public ArrayList<TreeNode> deleteLevel (TreeNode root, ArrayList<Integer> a) {
       //记录要删除的深度
       Set<Integer> set = new HashSet<Integer>();
       for (int num: a)
           set.add(num);
       //这里要加0，因为根节点是看作被被删除上一层的
       set.add(0);
       ArrayList<TreeNode> list = new ArrayList<TreeNode>();
       //BFS的模板
       Queue<TreeNode> queue = new LinkedList<TreeNode>();
       queue.add(root);
       int depth = 0;
       while(!queue.isEmpty()){
           int size = queue.size();
           depth++;
           for (int i = 0; i < size; i++){
               TreeNode node = queue.poll();  //注意这里弹出的是上一层的节点
               if(node.left != null){
                   queue.add(node.left);
               }
               if(node.right != null){
                   queue.add(node.right);
               } 
               //特殊例子 depth=2也就是在第二层,根节点要入链表
                              //其它情况 上一层被删除了，那么就要加上这一层的头节点   
               if (set.contains(depth-1)&&!set.contains(depth)){
                   list.add(node);
               }
               //要删除的上一层(因为上一层的左右节点都已经入队，此时我们只需要将左右指针置空即可)
               if(!set.contains(depth)&&set.contains(depth+1)){
                   node.left = null;
                   node.right = null;
               }
           }
       }
       return list;
    }

发表于 2022-08-03 14:30:39 回复(1)

程序员十年

写法一：

/**
 * struct TreeNode {
 *	int val;
 *	struct TreeNode *left;
 *	struct TreeNode *right;
 *	TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 * };
 */
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param root TreeNode类 
     * @param a int整型vector 
     * @return TreeNode类vector
     */
    typedef pair<TreeNode*, int> PII;
    vector<TreeNode*> deleteLevel(TreeNode* root, vector<int>& a) {
        // write code here
        vector<TreeNode*> ans;
        unordered_map<int,int> m;
        m[0]=1;    // 根节点是第一层，第0层是没有的，相当于被删除了的，所以设置为1，加这个特判后面如果根节点不删除的话，根节点才能够顺理成章的被录入答案ans中，以免漏掉根节点。
        
        for(auto num:a)
            m[num]=1;    // 将要删除的层数映射为1
        queue<PII> q;
        q.push({root, 1});
        while(q.size())    // 通过while循环进行层序遍历
        {
            PII p = q.front();
            q.pop();
            TreeNode* t = p.first;
            int high = p.second;
            if(t == nullptr)    // 如果这个节点是空的话（即不存在的话），就不用考虑它的左右子树了，因为空的是啥都没有的
                continue;
            if(m.find(high-1) != m.end() && m.find(high) == m.end())    // 挺过了前面的判断，到这里来的节点都不是空的了，那就判断它的上一个层是否为空，如果上一层为空，那么本层的所有节点就都可以作为根节点录入，并且一定都是树，有多少个根节点就有多少棵树
                ans.push_back(t);    // 既然一定是根节点，那就一定是答案的里的一棵树，将其添加到ans中
            
            /*
                map的find函数，如果找到了，就会返回一个iterator，m.end()表示容器末尾的下一位，如果iterator没有到容器末尾的话，就表明找到了
                iterator如果指向了容器末尾的下一位，则表示整个容器都已经搜索过了，没有找到high的映射
                find里面填的是map的第一个参数，如果找到的话，iterator是指向第二个参数，也就是第一个参数的映射
            */
            
            q.push({t->left, high+1});    // 这个while循环的本质就是在不断把一个节点的左节点和右节点添加到队列中，让while循环完成层序遍历的任务
            q.push({t->right, high+1});    // 队列中放的pair的第一个参数是一个节点，第二个参数是这个节点所在的层数，根节点是第一层，往下层数增大
            if(m.find(high+1) != m.end())    // 如果下层要被删掉，则此节点的左右节点都为空
            {
                t->left = nullptr;
                t->right = nullptr;
            }
        }
        return ans;
    }
};

写法二：

/**
 * struct TreeNode {
 *	int val;
 *	struct TreeNode *left;
 *	struct TreeNode *right;
 *	TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 * };
 */
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param root TreeNode类 
     * @param a int整型vector 
     * @return TreeNode类vector
     */
   typedef pair<TreeNode*, int> PII;
    vector<TreeNode*> deleteLevel(TreeNode* root, vector<int>& a) {
        // write code here
        vector<TreeNode*> ans;
        queue<PII> q;
        q.push({root, 1});
        unordered_map<int, int> m;
        m[0] = 1;
        
        for(auto c : a) {
            m[c] = 1;
        }
        
        while(q.size()) {
            auto p = q.front();
            q.pop();
            
            auto t = p.first;
            auto high = p.second;
            
            // 无论如果，都是要层序遍历完整棵树的所以，要把左右子树添加进队列
            if(t -> left != nullptr)
                q.push({t->left, high + 1});
            if(t -> right != nullptr)
                q.push({t->right, high +1});
            
            if(m.count(high + 1)){    // 截断，把树分开
                t->left = nullptr;    // 这里的t->left为空，不影响前面的t->left，因为它已经进队列了
                t->right = nullptr;    // 这里的t->left == nullptr更多是为了断开连接，让t这个节点指向空就行，至于后面要如何遍历，前面已经将t->left添加到队列中去，前面的t->left表示的是t的左子树的根节点
                // t->left是一个指针，它可以指向空，也可以指向一棵树，前面的t->left就是指向t的左子树，那这样的话，就相当于t的左子树的根节点
                // 而这里是让t->left指针指向空，目的是为了断开与后面子树的联系，相当于就删除了high+1这一层了
                // 注意！！一定要让t->left和t->right先进队列，再将其删除，因为只有这样，才能够遍历树，如果先删了，就断层，无法遍历整棵树了
            }
  
            if(m.count(high -1) && !m.count(high)) {
                ans.push_back(t);
            }
        }
        return ans;
    }
};

编辑于 2022-10-18 11:30:04 回复(1)

佛系指数100

goubi 牛客，不保留提交的代码，那就只能自己补个题解了

只要将a转换成set型，再进行广搜即可通过最后一个样例

如果不转换，只能通过12个

# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param root TreeNode类 
# @param a int整型一维数组 
# @return TreeNode类一维数组
#
class Solution:
    def deleteLevel(self , root: TreeNode, a: List[int]) -> List[TreeNode]:
        # write code here
                # 只需要将list型的a转换成set类型，就可以使得a在查找时时间复杂度降低
        a = set(a)
        def bfs(root,a):
                if root is None:
                        return 
                res = []
                count = 1
                if 1 not in a:
                        res = [root]
                queue = [root]
                while len(queue)!=0:
                        temp = []
                        for q in queue:
                                if q.left is not None:
                                        temp.append(q.left)
                                if q.right is not None:
                                        temp.append(q.right)
                                if (count+1) in a:
                                        q.left=None
                                        q.right=None
                        if count in a and (count+1) not in a:
                                res+=temp
                        count += 1
                        queue = temp
                return res
        return bfs(root,a)

发表于 2022-08-26 02:25:01 回复(0)

霸王龙v2

public ArrayList<TreeNode> deleteLevel (TreeNode root, ArrayList<Integer> a) {
        Set<Integer> set = new HashSet<>();
        for (int num : a) set.add(num);
        set.add(0);
        Queue<TreeNode> queue = new LinkedList<>();
        ArrayList<TreeNode> list = new ArrayList<>();
        queue.add(root);
        int depth = 0;
        
        while (!queue.isEmpty()) {
            int size = queue.size();
            depth++;
            while (size-- > 0) {
                TreeNode node = queue.poll();
                if (node.left != null)
                    queue.add(node.left);
                if (node.right != null) 
                    queue.add(node.right);
                if (set.contains(depth - 1) && !set.contains(depth))
                    list.add(node);
                if (!set.contains(depth) && set.contains(depth + 1)) {
                    node.left = null;
                    node.right = null;
                }
            }
        }
        return list;
    }

发表于 2022-07-14 22:31:32 回复(2)

奋斗的龙猫

import java.util.*;

/*
 * public class TreeNode {
 *   int val = 0;
 *   TreeNode left = null;
 *   TreeNode right = null;
 *   public TreeNode(int val) {
 *     this.val = val;
 *   }
 * }
 */

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param root TreeNode类 
     * @param a int整型ArrayList 
     * @return TreeNode类ArrayList
     */
    public ArrayList<TreeNode> deleteLevel (TreeNode root, ArrayList<Integer> a) {
        // write code here
        ArrayList<TreeNode> res = new ArrayList<>();
        if(root == null){
            return res;
        }
        if(a.size() == 0){
            res.add(root);
            return res;
        }
        
        Queue<TreeNode> q = new LinkedList<>();
        q.offer(root);
        List<ArrayList<TreeNode>> lists = new ArrayList<>();
        while(!q.isEmpty()){
            int size = q.size();
            ArrayList<TreeNode> list = new ArrayList<>();
            for(int i = 0; i < size; ++i){
                root = q.poll();
                list.add(root);
                if(root.right != null){
                    q.offer(root.right);
                }
                if(root.left != null){
                    q.offer(root.left);
                }
            }
            lists.add(list);
        }
        //将a倒序排序
        Collections.sort(a, (o1, o2) -> {return o2 - o1;});
        int size = lists.size();
        for(int level : a){
            //对于删除层level,需要将第level + 1层每个节点看成1棵子树，同时将level - 1层的子节点置为null
            //但lists中下标从0开始，所以第level层对应下标为level - 1，
            //第level + 1层对应下标为level, 第level - 1层对应level - 2
            if(lists.size() > level){
                //判断第level + 1层是否是移除的
                if(!a.contains(level + 1)){
                     res.addAll(lists.get(level));
                }
            }
            if(level > 1){
                //将第level - 1层的子节点置为null
                for(TreeNode node : lists.get(level - 2)){
                    node.left = null;
                    node.right = null;
                }
            }
        }
        //如果第1层不用删除，此时还需要将其添加到res中
        if(a.get(a.size() - 1) != 1){
            res.addAll(lists.get(0));
        }
        //将结果倒序(因为是逆序遍历level，再添加到res中的)
        Collections.reverse(res);
        return res;
    }
}

发表于 2023-01-26 12:29:29 回复(0)

牛客744479956号

难点总结

需要考虑根节点所在的树如何加入到答案数组中

除正常删除等级外还需考虑连续删除的问题

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param root TreeNode类
     * @param a int整型vector
     * @return TreeNode类vector
     */
    vector deleteLevel(TreeNode* root, vector& a) {
        // write code here
        unordered_set dic(a.begin(),a.end());
        vector ans;
        int level=0;
        TreeNode* dummp=new TreeNode(0);
        dummp->left=root;
        queue q;
        q.push(dummp);
        if(!dic.count(1))ans.push_back(root);
        while(!q.empty()){
            int sz=q.size();
            for(int i=0;i<sz;i++){
                TreeNode* tmp=q.front();q.pop();
                if(tmp->left){
                    q.push(tmp->left);
                }
                if(tmp->right){
                    q.push(tmp->right);
                }
                if(dic.count(level)&&!dic.count(level+1)){
                    if(tmp->left)ans.push_back(tmp->left);
                    if(tmp->right)ans.push_back(tmp->right);
                }
                if(dic.count(level+1)){
                    tmp->left=nullptr;
                    tmp->right=nullptr;
                }
            }
            level++;
        }
        return ans;

    }
};

发表于 2022-09-19 16:12:30 回复(0)

打水漂

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param root TreeNode类
     * @param a int整型ArrayList
     * @return TreeNode类ArrayList
     */
    private ArrayList<TreeNode> res;
    public ArrayList<TreeNode> deleteLevel (TreeNode root, ArrayList<Integer> a) {
        // write code here
        res = new ArrayList<>();
        Set<Integer> set = new HashSet<>();
        for(int i = 0; i < a.size(); i++) set.add(a.get(i));
        set.add(0);
        Queue<TreeNode> q = new LinkedList<>();
        int height = -1;
        TreeNode newRoot = new TreeNode(0);
        newRoot.left = root;
        q.add(newRoot);
        while(!q.isEmpty()) {
            int size = q.size();
            height++;
            while(size-- > 0) {
                TreeNode front = q.poll();
                if(front.left != null) q.add(front.left);
                if(front.right != null) q.add(front.right);
                if(!set.contains(height) && set.contains(height + 1)) {
                    front.left = null;
                    front.right = null;
                }
                if(set.contains(height) && !set.contains(height + 1)) {
                    if(front.left != null) {
                        res.add(front.left);
                    }
                    if(front.right != null) {
                        res.add(front.right);
                    }
                }
            }
        }
        return res;
    }
}

发表于 2022-08-14 16:09:47 回复(0)

苏觅云

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param root TreeNode类
     * @param a int整型vector
     * @return TreeNode类vector
     */
    map<int, vector<TreeNode *>> cache;
    unordered_set<int> st;

    vector<TreeNode *> deleteLevel(TreeNode *root, vector<int> &a) {
        // write code here
        st.insert(0);
        for (int i : a) {
            st.insert(i);
        }
        dfs(root, 1);
        vector<TreeNode *> ans;
        for (auto &kv : cache) {
            for (auto &v : kv.second) {
                ans.emplace_back(v);
            }
        }
        return ans;
    }

    void dfs(TreeNode *root, int depth) {
        if (root == nullptr) {
            return;
        }
        bool preDel = (st.find(depth - 1) != st.end());
        bool nowDel = (st.find(depth) != st.end());
        bool nxtDel = (st.find(depth + 1) != st.end());
        if ((!nowDel) && preDel) {
            cache[depth].emplace_back(root);
        }
        dfs(root->left, depth + 1);
        dfs(root->right, depth + 1);
        if (nxtDel) {
            root->left = nullptr;
            root->right = nullptr;
        }
    }

};

发表于 2022-08-01 14:27:52 回复(0)

不知77

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param root TreeNode类
     * @param a int整型vector
     * @return TreeNode类vector
     */
     //  在a中查找是否包含目标值
     bool find(vector<int> a,int target){
         for(int i=0;i<a.size();i++){
             if(a[i] == target){
                 return true;
             }
         }
        return false;
     }
    vector<TreeNode*> deleteLevel(TreeNode* root, vector<int>& a) {
        queue<pair<TreeNode*,int>> q;   //节点和层数
        q.push({root,1});
        vector<TreeNode*> ans;
        if (!find(a,1)){
            ans.push_back(root);
        }
        while(!q.empty()){
            auto [node,deep] = q.front();
            q.pop();
            if (node == nullptr){
                continue;
            }
            // 如果这层的上一层被删除了并且这层不需要被删，它就是需要的答案
            if (find(a, deep - 1) && !find(a, deep)){
                ans.push_back(node);
            }
            q.push({node->left, deep + 1});
            q.push({node->right, deep + 1});
            // 如果这层的下一层被删除了，这层就是末尾，左右节点全置空
            if (find(a, deep + 1)){
                node->left = nullptr;       
                node->right = nullptr;
            }
        }
        return ans;
    }
};

发表于 2022-07-22 16:42:56 回复(0)

球球大厂收了我吧


import java.util.*;

/*
 * public class TreeNode {
 *   int val = 0;
 *   TreeNode left = null;
 *   TreeNode right = null;
 *   public TreeNode(int val) {
 *     this.val = val;
 *   }
 * }
 */

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param root TreeNode类 
     * @param a int整型ArrayList 
     * @return TreeNode类ArrayList
     */
    public ArrayList<TreeNode> deleteLevel (TreeNode root, ArrayList<Integer> a) {
        // write code here
        ArrayList<TreeNode> res= new ArrayList<>();
        if (root==null) return res;
        //这是二叉树行遍历 把每一行称之为索引行
        List<List<TreeNode>> help = levelorder(root);
        //这个变量是指向了当前树的根节点所在的层数
        //举个例子 假如第3层被切掉了（索引为2的行）
        //现在rootIndex还在0 把0行的树节点都假如到res集合中
        //然后更新rootIndex变成3=（2+1） 下次就从3开始 3上面的不考虑了
        //还不明白就看下面代码
        int rootIndex=0;
        Collections.sort(a);
        for (int cur  : a) {
            //对于每个cur 把他变成索引行对应的值 也就是cur-1
            cur=cur-1;
            //如果当前切除了根 不用管直接下一位
            if (cur==rootIndex){
                rootIndex++;
                continue;
            }
            //不是的话就要找到切除行的上一行 然后把每个节点的左后孩子都置null
            List<TreeNode> list = help.get(cur - 1);
            for (TreeNode node : list) {
                node.left=null;
                node.right=null;
            }
            //然后加入当前rootIndex所在的节点 继续下一轮
            for (TreeNode node : help.get(rootIndex)) {
                res.add(node);
            }
            rootIndex=cur+1;
        }
       //最后看情况做节点的收尾补偿工作
        if (rootIndex<help.size()){
            for (TreeNode node : help.get(rootIndex)) {
                res.add(node);
            }
        }
        return res;
    }
    //这个函数是二叉树行遍历  大家肯定都会
    public  List<List<TreeNode>> levelorder(TreeNode root) {
        List<List<TreeNode>> res = new ArrayList<>();
        if (root == null) return res;
        Deque<TreeNode> q = new LinkedList<>();

        q.addLast(root);
        while (!q.isEmpty()) {
            int size = q.size();
            List<TreeNode> list = new ArrayList<>();
            for (int i = 0; i < size; i++) {
                TreeNode cur = q.pollLast();
                list.add(cur);
                if (cur.left != null) q.addFirst(cur.left);
                if (cur.right != null) q.addFirst(cur.right);

            }
            res.add(list);
        }
        return res;

    }
}

发表于 2022-07-13 11:20:45 回复(0)

好难取个名字

import java.util.*;

/*
 * public class TreeNode {
 *   int val = 0;
 *   TreeNode left = null;
 *   TreeNode right = null;
 *   public TreeNode(int val) {
 *     this.val = val;
 *   }
 * }
 */

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param root TreeNode类 
     * @param a int整型ArrayList 
     * @return TreeNode类ArrayList
     */
    public ArrayList<TreeNode> deleteLevel (TreeNode root, ArrayList<Integer> a) {
        // write code here
        HashSet<Integer> set = new HashSet<>();
        for(int val : a) set.add(val);
        set.add(0);
        ArrayList<TreeNode> list = new ArrayList<>();
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        int preNum = 1,current_num = 0,current_deep = 1;
        while(queue.size() != 0){
            TreeNode node = queue.poll();
            --preNum;
            if(node.left != null){
                queue.offer(node.left);
                ++current_num;
            }
            if(node.right != null){
                queue.offer(node.right);
                ++current_num;
            }
            if(set.contains(current_deep-1) && set.contains(current_deep) == false){
                list.add(node);
            }
            if(set.contains(current_deep) == false && set.contains(current_deep+1)){
                node.left = null;
                node.right = null;
            }
            if(preNum == 0){
                preNum = current_num;
                current_num = 0;
                ++current_deep;
            }
            
        }
        return list;
    }
}

发表于 2022-07-02 14:49:31 回复(0)