[1110] Delete Nodes And Return Forest

已經參考別人的寫法了～只是把C++翻成C，結果遭遇巨大困難Orz

我真的沒有天份吧唉

原本寫了一堆的if else 跟calloc ，最後的最後才發現，

什麼原來只需要一開始的pointer to tree的 return array，裡面的node 都不需要再calloc 一次

它們本來就長在root 裡了！！！！！

縮以也就是說不用額外複製一份去return array，也不會發生要被delete掉的人還是有左右 child 的問題。天啊我真是太嫩了啊！！！！！！！！（跪地喊）

於是各種刪除之後行數就變的很少了，但完全是個我寫不出來的東西啊～～～～（痛哭）

1. 傳入參數: 這個是不是root 。除了最一開始的root，當遍歷整顆樹的時候，遇到要刪除的人，它的小孩會分別變成root。因此當你看到進入dfs時root is tree的時候，它其實是parent call進來的！！！ （如果刪的是leaf 那就直接拿掉就可以了。）

2.是root的人，它必需要指去新的return array index. 因為是新的一棵樹！

3.因為dfs的 特性（？），雖然是recursive的寫法，一旦遇到要刪除的人，它下面會是新的樹，它上面會return NULL回去切掉這個連結，（斷開連結？！）所以recursive 下去再回來之後也不會影響return array 的index. (就是原本的樹拆成好幾組，分別把return array 依index 指去它們的新root)

靠杯啊太難了吧！！！！！！！！！！！

/**

* Definition for a binary tree node.

* struct TreeNode {

* int val;

* struct TreeNode *left;

* struct TreeNode *right;

* };

*/

/**

* Note: The returned array must be malloced, assume caller calls free().

*/

int idx;

struct TreeNode** ret;

struct TreeNode* mark(struct TreeNode* root, bool *hash, bool is_root)

{

if (root == NULL)

return NULL;

if (is_root && !hash[root->val])

ret[idx++] = root;

root->left = mark(root->left, hash, hash[root->val]);

root->right = mark(root->right, hash, hash[root->val]);

return (hash[root->val])? NULL : (root);

}

struct TreeNode** delNodes(struct TreeNode* root, int* to_delete, int to_deleteSize, int* returnSize){

bool *hash = calloc (1001, sizeof(bool));

for (int i=0; i<to_deleteSize; i++)

hash[to_delete[i]]= true;

ret = calloc (1000, sizeof (struct TreeNode*));

idx = 0;

mark(root, hash, true);

*returnSize = idx;

return ret;

}