首页 > 其他分享 >【每日一题】[1110. 删点成林]

【每日一题】[1110. 删点成林]

时间:2023-05-30 13:11:06浏览次数:45  
标签:right TreeNode 成林 val 1110 hash 删点 root left

1110. 删点成林

给出二叉树的根节点 root,树上每个节点都有一个不同的值。

如果节点值在 to_delete 中出现,我们就把该节点从树上删去,最后得到一个森林(一些不相交的树构成的集合)。

返回森林中的每棵树。你可以按任意顺序组织答案。

示例 1:

img
输入:root = [1,2,3,4,5,6,7], to_delete = [3,5]
输出:[[1,2,null,4],[6],[7]]

示例 2:

输入:root = [1,2,4,null,3], to_delete = [3]
输出:[[1,2,4]]

提示:

  • 树中的节点数最大为 1000。
  • 每个节点都有一个介于 1 到 1000 之间的值,且各不相同。
  • to_delete.length <= 1000
  • to_delete 包含一些从 1 到 1000、各不相同的值。
层序遍历
  • 用一个map存储节点的父节点,如果当前节点是删除节点,则
    • 父节点的左或右指向为null
    • 子节点不为空则添加到ans
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    
    public List<TreeNode> delNodes(TreeNode root, int[] to_delete) {
        Deque<TreeNode> que = new LinkedList<>();
        List<TreeNode> ans = new ArrayList<TreeNode>();
        HashMap<TreeNode, TreeNode> pre = new HashMap<>();

        var hash = new boolean[1000+1];
        for(var item : to_delete) {
            hash[item] = true;
        }

        if(root == null) {
            return ans;
        }

        que.add(root);
        if(!hash[root.val]) {
            ans.add(root);
        }

        while(!que.isEmpty()) {
            var size = que.size();
            while(size-- > 0) {
                var poll = que.poll();
                var left = poll.left;
                var right = poll.right;
                var parent = pre.get(poll);

                if(parent != null && hash[poll.val]) {
                    if(parent.left == poll) {
                        parent.left = null;
                    } else {
                        parent.right = null;
                    }
                }

                if(left != null) { 
                    if(hash[poll.val] && !hash[left.val]) {
                        ans.add(left);
                    }
                    pre.put(left, poll);
                    que.add(left);
                }

                if(right != null) {
                    if(hash[poll.val] && !hash[right.val]) {
                        ans.add(right);
                    }
                    pre.put(right, poll);
                    que.add(right);
                }
            }
        }

        return ans;
    }
}
后序遍历
  • 和上面的思想大致相同,只不过不需要map来存储父节点了,因为后序遍历能够知道父节点是哪个
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    List<TreeNode> ans = new ArrayList<TreeNode>();
    boolean[] hash = new boolean[1000+1];

    public void postOrder(TreeNode root) {
        if(root == null) {
            return ;
        }
        var left = root.left;
        var right = root.right;
        postOrder(left);
        postOrder(right);

        if(hash[root.val]) {
            if(left != null && !hash[left.val]) {
                ans.add(left);
            }

            if(right != null && !hash[right.val]) {
                ans.add(right);
            }
        }

        if(left != null && hash[left.val]) {
            root.left = null;
        }

        if(right != null && hash[right.val]) {
            root.right = null;
        }
    }
    
    public List<TreeNode> delNodes(TreeNode root, int[] to_delete) {
        for(var item : to_delete) {
            hash[item] = true;
        }
        if(!hash[root.val]) {
            ans.add(root);
        }
        postOrder(root);
        return ans;
    }
}

标签:right,TreeNode,成林,val,1110,hash,删点,root,left
From: https://www.cnblogs.com/tod4/p/17442956.html

相关文章

  • 1110 Complete Binary Tree(附测试点2,3,4,6分析)
    题目:Givenatree,youaresupposedtotellifitisacompletebinarytree.InputSpecification:Eachinputfilecontainsonetestcase.Foreachcase,thefirstlinegivesapositiveinteger N (≤20)whichisthetotalnumberofnodesinthetree--andh......
  • CSCI 1110: 算法问题
    CSCI1110:Assignment0Due:11:59pm,Friday,May12,2023Thepurposeofthisassignmentistoallowyoutoself-assessyourreadinessforthiscourse.Ifyouarestrugglingtocompletethisassignment,andhavenottakenCSCI1100orCSCI1105,pleasecon......
  • UVA11107 Life Forms
    怎么没有正常的后缀数组二分的题解啊给定\(n\)个字符串,求出最长的,在多于\(\left\lfloor\frac{n}{2}\right\rfloor\)个字符串中出现的子串,并按照字典序从小到大输出。\(n\leq100\),\(|S|\leq1000\),根据套路可以将所有字符串连成一个,不同的字符串用特殊符号隔开,然后建出新......
  • 1110 完全二叉树
    给定一个树,请你判断它是否是完全二叉树。输入格式第一行包含整数 N,表示树的结点个数。树的结点编号为 0∼N−1。接下来 N 行,每行对应一个结点,并给出该结点的左右子结点的编号,如果某个子结点不存在,则用 - 代替。输出格式如果是完全二叉树,则输出 YES 以及最后一个结点......
  • PAT Basic 1110. 区块反转
    PATBasic1110.区块反转1.题目描述:给定一个单链表 \(L\),我们将每 \(K\) 个结点看成一个区块(链表最后若不足 \(K\) 个结点,也看成一个区块),请编写程序将 \(L\) 中所有区块的链接反转。例如:给定 \(L\) 为\(1→2→3→4→5→6→7→8\),\(K\) 为3,则输出应该为\(7→8→4......
  • Semi-prime H-numbers UVA - 11105
     所有形如4n+1(n为非负整数)的数叫H数。定义1是唯一的单位H数,H素数是指本身不是1,且不能写成两个不是1的H数的乘积。H-半素数是指能写成两个H素数的乘积的H数(这两个数可以相同也可以不同)。 例如,25是H-半素数,但125不是。输入一个H数h(h≤1000001),输出1~h之间有多少个H-半素数。......
  • 2203031110 黄正淳
    #include<stdio.h>intmain(){inta,b,temp;scanf("%d%d",&a,&b);temp=a;a=b;b=temp;printf("%d%d",a,b);return0;}#include<stdio.h>intmain(......
  • exp导数据时报错ORA-01578 ORA-01110
    问题描述:exp导数据时报错ORA-01578ORA-01110,如下所示:数据库:oracle19.12多租户1、异常重现[oracle@dbserver~]$expora1/ora1@orclpdbfile=emp.dmptables=emplog=exp......
  • <Verilog学习>Verilog设计“111”检测器与“01110”检测器并测试所有情况
    使用Quartus+modelsim完成本次设计目录1."111"检测器分析代码实现Testbench结果2."01110"检测器分析代码实现Testbench结果1."111"检测器分析分析题目,得到其有限状......
  • 数据库在执行全库恢复后,open时报错ORA-01113、ORA-01110 ORA-00312 ORA-01113
    问题描述:数据库在执行全库恢复后,open时报错ORA-01113、ORA-01110ORA-00312ORA-01113系统:Anolis7.9数据库:oracle11.2.0.41、问题描述数据库在执行全库恢复后,open时报错OR......