Google电面题删除节点后的森林

看到一个电面的题目 题目是 给一个tree 给一个api api的输入是一个treenode 返回bool 告诉你这个node是否该被删除 返回删除点后的森林 第二问是 告诉你原来的树是bst 并且告诉你被删除的node list和删除后森林root的node list 要你还原这个树。可以还原多个,返回一个即可

怎样的node是应该删除的

前面理解错了,那么是把所有node都调用一遍API,看下是不是该删吗?一个node被删,就形成一个新树。dfs走一下就可以了吧。
这题好眼熟。

这个应该是利用bst的性质,知道被删的node的位置。被删’的node应该就是连接所有森林root的。你画几个例子就能摸出规律了。这种题多试几个例子就行。

既然是bst,那么如果你把所有森林的node的值,以及被删的node值,放一起成为一个数组,然后sort。这个数组就是该bst做inorder traversal相应的。
下一步可以做inorder traversal,并找到相应的森林的root,碰到缺的地方应该就是被删的node,来补全。

应该这个题是一个意思:
Return the forest after travel the treenode and delete the node as it needed by calling the shouldDeleteNode

      A
    /   \
   (B)   (E)
  /   \    \
  D    Y    Z

Ret: D; Y; A; Z