https://docs.google.com/document/d/1qxA2wps0IhVRWULulQ55W4SGPMu2AE5MkBB37h8Dr58/
第一轮是给一个二叉树，然后再给一个list的TreeNode，这个list里的TreeNode是肯定在二叉树里的，然后要把这些TreeNode删除，最后返回一个原二叉树删除这些TreeNode后得到的Forest
举个例子，如果二叉树如下：
A
/ \
[B] C
/ \ \
D E [F]
方括号内的TreeNode是要删除的，最后返回的Forest是[A, D, E]。
这道题我用recursion做的，输入参数一个是TreeNode，一个是它的parent是不是被删除的boolean。然后要我给出不同的test case
根节点漏掉了，拿上面的例子来说，A节点最后没被放到结果中去
17. N叉树，要求删一些node，返回list of roots 高频 8次
More Detail : 给一个tree有红的node有蓝的node，把红的去掉后剩下一堆零零散散的tree， 返回这些tree的node，只要node，不要children，也就是说把这个node的children设置成null然后加到list里。
参数是这个树的root。找到所有的红点然后delete掉，去掉这些红点之后就会把一个tree变成散落的几个tree，然后返回这几个tree的root。直接一个recursive判断一下，如果这个node是红点的话就ignore 掉再去判断这个node的children，如果这个node是蓝点的话，要看这个蓝点的parent是不是个红点，是的话，这个蓝点就是散落的tree中其中一个tree的root。
思路：简单BFS。。不应是dfs?
想问一下这题返回的顺序重要吗？
没想到怎么做，有没有大佬写了code能发一下的?感激不尽
(Provider: fill your name)
private void dfs(Node root, Node parent, List<Node> res) {
if (root == null) {
return;
}
if ((parent == null || parent.color == red) && root.color != red) {
res.add(root);
}
for (Node children : root.children) {
dfs(child, root, res);
}
}
public void dfsHelp (Node root, List<Node> res) {
if (root == null) {
return;
}
if (root.isRed) {
for (Node child:root.childrens) {
if (!child.isRed) {
res.add(child);
}
dfsHelp(child, res);
}
} else {
res.add(root);
Iterator<Node> it = root.childrens.iterator();
while (it.hasNext()) {
Node child = it.next();
if (child.isRed) {
root.childrens.remove(child);
}
dfsHelp(child, res);
}
}
}
class TreeNode(object):
def __init__(self, val, color):
self.val = val
self.color = color
self.children = []
class Solution(object):
def listOfRoots(self, root):
if not root: return []
ans = []
def dfs(node, parent):
if not node: return
if node.color == 'b':
if parent.color == 'r': ans.append(node.val)
// should check if parent is None
else: ans.append(-1)//这里加上负一是为什么？
for child in node.children:
dfs(child, node)
dfs(root, None)
return ans
删除node返回森林
第一轮是给一个二叉树，然后再给一个list的TreeNode，这个list里的TreeNode是肯定在二叉树里的，然后要把这些TreeNode删除，最后返回一个原二叉树删除这些TreeNode后得到的Forest
举个例子，如果二叉树如下：
A
/ \
[B] C
/ \ \
D E [F]
方括号内的TreeNode是要删除的，最后返回的Forest是[A, D, E]。
这道题我用recursion做的，输入参数一个是TreeNode，一个是它的parent是不是被删除的boolean。然后要我给出不同的test case
思路：
简单的dfs
如果当前节点需要被删除，递归进入它的左右子树得到左右子树被删除节点后的新树，如果不为null则加入list，然后由于当前节点被删除了，返回null
如果当前节点不需要被删除，左右子树递归，然后返回当前节点
code:
Provider: null
public TreeNode dfsUtil(TreeNode root, Set<TreeNode> deleted, List<TreeNode> res) {
if(root == null) return null;
if(deleted.contains(root)) {
TreeNode left = dfsUtil(root.left, deleted, res);
TreeNode right = dfsUtil(root.right, deleted, res);
if(left != null) res.add(left);
if(right != null) res.add(right);
return null;
} else {
root.left = dfsUtil(root.left, deleted, res);
root.right = dfsUtil(root.right, deleted, res);
return root;
}
}
