Created
March 21, 2020 08:44
-
-
Save IvoIvanov77/894e3872db1da55aa5e47b2fb68fe1fb to your computer and use it in GitHub Desktop.
solutions
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
package implementations; | |
import interfaces.AbstractTree; | |
import java.util.ArrayDeque; | |
import java.util.ArrayList; | |
import java.util.Collections; | |
import java.util.List; | |
public class Tree<E> implements AbstractTree<E> { | |
private E key; | |
private Tree<E> parent; | |
private List<Tree<E>> children; | |
private int counter; | |
private Tree<E> result; | |
private int sum; | |
public Tree(E key) { | |
this.key = key; | |
this.children = new ArrayList<>(); | |
} | |
@Override | |
public void setParent(Tree<E> parent) { | |
this.parent = parent; | |
} | |
@Override | |
public void addChild(Tree<E> child) { | |
this.children.add(child); | |
} | |
@Override | |
public Tree<E> getParent() { | |
return this.parent; | |
} | |
@Override | |
public E getKey() { | |
return this.key; | |
} | |
@Override | |
public String getAsString() { | |
StringBuilder builder = new StringBuilder(); | |
dfsString(this, builder, 0, " "); | |
return builder.toString().trim(); | |
} | |
private void dfsString(Tree<E> root, StringBuilder builder, int level, String delimiter) { | |
builder.append(String.join("", Collections.nCopies(level, delimiter))) | |
.append(root.key) | |
.append("\r\n"); | |
level ++; | |
for (Tree<E> child : root.children) { | |
dfsString(child, builder, level, delimiter); | |
} | |
} | |
@Override | |
public List<E> getLeafKeys() { | |
List<E> result = new ArrayList<>(); | |
ArrayDeque<Tree<E>> queue = new ArrayDeque<>(); | |
queue.offer(this); | |
while (!queue.isEmpty()) { | |
Tree<E> tree = queue.poll(); | |
if(tree.children.isEmpty()) { | |
result.add(tree.key); | |
} else { | |
for (Tree<E> child : tree.children) { | |
queue.offer(child); | |
} | |
} | |
} | |
return result; | |
} | |
@Override | |
public List<E> getMiddleKeys() { | |
List<E> result = new ArrayList<>(); | |
ArrayDeque<Tree<E>> queue = new ArrayDeque<>(); | |
queue.offer(this); | |
while (!queue.isEmpty()) { | |
Tree<E> tree = queue.poll(); | |
if(!tree.children.isEmpty() && tree.parent != null) { | |
result.add(tree.key); | |
} | |
for (Tree<E> child : tree.children) { | |
queue.offer(child); | |
} | |
} | |
return result; | |
} | |
@Override | |
public Tree<E> getDeepestLeftmostNode() { | |
dfsLeftmostNode(this, 0); | |
return result; | |
} | |
private void dfsLeftmostNode(Tree<E> root, int level) { | |
if(level > counter) { | |
counter = level; | |
result = root; | |
} | |
for (Tree<E> child : root.children) { | |
dfsLeftmostNode(child, level + 1); | |
} | |
} | |
@Override | |
public List<E> getLongestPath() { | |
List<E> path = new ArrayList<>(); | |
dfsLongestPath(this, 0, path); | |
return path; | |
} | |
private void dfsLongestPath(Tree<E> root, int level, List<E> path) { | |
if(level >= path.size()) { | |
if(!path.isEmpty()) { | |
path.set(path.size() - 1, root.parent.key); | |
} | |
path.add(root.key); | |
} | |
for (Tree<E> child : root.children) { | |
dfsLongestPath(child, level + 1, path); | |
} | |
} | |
@Override | |
public List<List<E>> pathsWithGivenSum(int sum) { | |
List<List<E>> result = new ArrayList<>(); | |
pathsWithGivenSum(this, 0, sum, 0, new ArrayList<>(), result); | |
return result; | |
} | |
private void pathsWithGivenSum(Tree<E> root, int level, int sum, int currentSum, | |
List<E> path, List<List<E>> result) { | |
if(level >= path.size()) { | |
path.add(root.key); | |
currentSum += (Integer) root.key; | |
} | |
if(root.children.isEmpty()) { | |
if (currentSum == sum) { | |
result.add(path); | |
} | |
currentSum = 0; | |
path = new ArrayList<>(); | |
} | |
for (Tree<E> child : root.children) { | |
pathsWithGivenSum(child, level + 1, sum, currentSum, path, result); | |
} | |
} | |
@Override | |
public List<Tree<E>> subTreesWithGivenSum(int sum) { | |
List<Tree<E>> result = new ArrayList<>(); | |
dfsTreesWithGivenSum(this, result, sum); | |
return result; | |
// return bfsTreesWithGivenSum(this, sum); | |
} | |
private void treeSum(Tree<E> tree) { | |
sum += (int) tree.key; | |
for (Tree<E> child : tree.children) { | |
treeSum(child); | |
} | |
} | |
private int getSum(Tree<E> tree) { | |
sum = 0; | |
treeSum(tree); | |
return sum; | |
} | |
private void dfsTreesWithGivenSum(Tree<E> root, List<Tree<E>> result, int sum) { | |
if( getSum(root) == sum) { | |
result.add(root); | |
} | |
for (Tree<E> child : root.children) { | |
dfsTreesWithGivenSum(child, result, sum); | |
} | |
} | |
private List<Tree<E>> bfsTreesWithGivenSum(Tree<E> root, int sum) { | |
List<Tree<E>> result = new ArrayList<>(); | |
ArrayDeque<Tree<E>> queue = new ArrayDeque<>(); | |
queue.offer(root); | |
while (!queue.isEmpty()) { | |
Tree<E> tree = queue.poll(); | |
if(getSum(tree) == sum) { | |
result.add(tree); | |
} | |
for (Tree<E> child : tree.children) { | |
queue.offer(child); | |
} | |
} | |
return result; | |
} | |
} | |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment