sandak
BAN USERpublic class Solution {
public static class Node {
int value;
Node left;
Node right;
}
public int timeTilBurns(Node root, Node start) {
if (root == null || start == null) return 0;
Map<Node, Node> nodesAndParents = new HashMap();
findParensForAllNodes(root, null, nodesAndParents);
int time = 0; // current moment
List<Node> currentBurningNodes = new ArrayList() {{ add(start); }};
while (!nodesAndParents.isEmpty()) {
List<Node> newCurrentBurningNodes = new ArrayList();
// infect neighbours
while (!currentBurningNodes.isEmpty()) {
Node currentBurning = currentBurningNodes.remove(0);
// add infected nodes
Node parent = nodesAndParents.get(currentBurning);
if (parent != null) newCurrentBurningNodes.add(parent);
if (currentBurning.left != null) newCurrentBurningNodes.add(currentBurning.left);
if (currentBurning.right != null) newCurrentBurningNodes.add(currentBurning.right);
nodesAndParents.remove(currentBurning);
}
time++;
currentBurningNodes = newCurrentBurningNodes;
}
return time;
}
public void findParensForAllNodes(Node node, Node parent, Map<Node, Node> map) {
if (node != null) {
map.put(node, parent);
findParensForAllNodes(node.left, node, map);
findParensForAllNodes(node.right, node, map);
}
}
}
class Node {
public int value;
public Node right;
public Node left;
}
int minLevel(Node root) {
if (root == null) return -1;
List<int> levelsums = calcLevelSums(root); // O(n)
retun levelWithMinSum(levelsums) + 1; // wc - O(n)
}
ist<int> calcLevelSums(Node root) {
List<int> levelSums = new ArrayList();
List<Tuple<int, Node>> nodesToProcess = new ArrayList();
nodesToProcess.put(new Tuple(0, root));
// extremely not balanced tree - O(n)
// balanced tree -
// leaves n/2, with reallocation: 1 + 2 + 4 + ... + n = 1 * (2 ^ log(n) - 1) / 2 = n
while (!nodesToProcess.isEmpty()) {
Tuple<int, Node> curr = nodesToProcess.delete(nodesToProcess.size()-1);
int level = curr.getX();
Node node = curr.getY();
int sum = levelSums.get(level) + node.value;
levelSums.set(level, sum);
if (node.left != null) {
nodesToProcess.put(new Tuple(level+1, node.left));
}
if (node.right != null) {
nodesToProcess.put(new Tuple(level+1, node.right));
}
}
return levelSums;
}
int levelWithMinSum(List<int> list) {
if (list == null || list.size() == 0) {
return Integer.MIN_VALUE;
}
int minInd = 0;
for (int i = 0; i < list.size(); i++) {
if (list.get(i) < list.get(minInd)) {
minInd = i;
}
}
return minInd;
}
O(N^2) time, no additional space.
less than O(N^2) time it is not possible to solve the problem.
- sandak October 11, 2017