1110. 删点成林
给出二叉树的根节点 root，树上每个节点都有一个不同的值。
如果节点值在 to_delete 中出现，我们就把该节点从树上删去，最后得到一个森林（一些不相交的树构成的集合）。
返回森林中的每棵树。你可以按任意顺序组织答案。
示例 1：
输入：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;
}
}