| 110 | } |
| 111 | |
| 112 | int burnTree(Node* targetNode, map<Node*, Node*> nodeToParent){ |
| 113 | map<Node*, bool> visited; |
| 114 | queue<Node*> q; |
| 115 | q.push(targetNode); |
| 116 | visited[targetNode] = true; |
| 117 | |
| 118 | int ans = 0; |
| 119 | |
| 120 | while(!q.empty()){ |
| 121 | bool flag = 0; |
| 122 | int size = q.size(); |
| 123 | for(int i=0; i<size; i++){ |
| 124 | Node* front = q.front(); |
| 125 | q.pop(); |
| 126 | |
| 127 | if(front->left && !visited[front->left]){ |
| 128 | flag = 1; |
| 129 | q.push(front->left); |
| 130 | visited[front->left] = 1; |
| 131 | } |
| 132 | if(front->right && !visited[front->right]){ |
| 133 | flag = 1; |
| 134 | q.push(front->right); |
| 135 | visited[front->right] = 1; |
| 136 | } |
| 137 | if(nodeToParent[front] && !visited[nodeToParent[front]]){ |
| 138 | flag = 1; |
| 139 | q.push(nodeToParent[front]); |
| 140 | visited[nodeToParent[front]] = 1; |
| 141 | } |
| 142 | } |
| 143 | if(flag){ |
| 144 | ans++; |
| 145 | } |
| 146 | } |
| 147 | return ans; |
| 148 | } |
| 149 | |
| 150 | int minTime(Node* root, int target){ |
| 151 | map<Node*, Node*> nodeToParent; |