# Description:

linear time delete subtree。改变TreeNode的valid值及其所有的subtree，更新整个tree node数量。

## Example:

``````Note
``````

# Code:

``````#include <iostream>
#include <vector>
#include <climits>
#include <cassert>
#include <unordered_set>

using namespace std;

struct TreeNode{
int parent;
int val;
bool valid;
};

void setNode(TreeNode& node, int val, int p){
node.parent=p;
node.val=val;
node.valid=true;
}

vector<TreeNode> setTree(int n){
vector<TreeNode> tree_arr(n);
setNode(tree_arr[0], 1, -1);
setNode(tree_arr[1], 1, 0);
setNode(tree_arr[2], 1, 0);
setNode(tree_arr[3], 1, 1);
setNode(tree_arr[4], 1, 1);
setNode(tree_arr[5], 1, 1);
setNode(tree_arr[6], 1, 2);
setNode(tree_arr[7], 1, 2);
setNode(tree_arr[8], 1, 4);
setNode(tree_arr[9], 1, 5);
setNode(tree_arr[10], 1, 6);
setNode(tree_arr[11], 1, 8);
setNode(tree_arr[12], 1, 9);
setNode(tree_arr[13], 1, 9);

return tree_arr;
}

// return bool, false means its parent is visited and deleted, true mean it is not
bool dfs(vector<TreeNode>& tree_arr, int i, int idelete, int& count, unordered_set<int>& visited){
if(visited.find(i)!=visited.end()) return tree_arr[i].valid;

visited.insert(i);
if(i==idelete){
tree_arr[i].valid=false;
count--;
return false;
}

if(tree_arr[i].parent==-1){
return true;
}

bool flag = dfs(tree_arr, tree_arr[i].parent, idelete, count, visited);
if(!flag){
tree_arr[i].valid=false;
count--;
}

return flag;
}

// Return the remaining number of tree nodes
int deleteSubTree(vector<TreeNode>& tree_arr, int idelete){

int count=tree_arr.size();
unordered_set<int> visited;

for(int i=0; i<tree_arr.size(); i++){
if(visited.find(i)==visited.end()){
dfs(tree_arr, i, idelete, count, visited);
}
}

return count;
}

int main(){
vector<TreeNode> tree_arr = setTree(14);

cout<<"Remaining nodes: "<<deleteSubTree(tree_arr, 6)<<endl;
}
``````