Delete Subtree

Description:

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

一个Array[Nodes]. Node包含［parent，value，valid］，给一个index，删除一个子树，然后更新这个valid，true表示还在，false表示删了，让我不能malloc空间，但是可以递归。 要注意在test case里面，他有看size，所以每次删除了还要减一下size。还有如果删除的点是root的case

Example:

Note

Idea:

与Docker Build Order和Linked List Cycle思想一样，用一个visited来记录是否visit，并且dfs的时候返回状态，以此来修改tree的valid。

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;
}