Учете да работите с ИИ, момци! Първия път му исках да разпише дърво, да го напълни с рандом номера, и да изкара път от корен до лист, който има максимална стойност. Нещо подобно са ми давали на интервю. После го накарах да изпринти дървото в конзолата, и си модифицира кода.
Аз вече ще ходя с чата, по такива мероприятия. Интересното е, че в нета само на едно място, в един форум, имаше разписано дърво в толкова лаконичен вид. Все едно, че ИИ копира оттам.
import java.util.*;
public class MaxSumPathTree {
static class Node {
int val;
Node left, right;
Node(int val) {
this.val = val;
this.left = null;
this.right = null;
}
}
// Method to print the binary tree in text console
public static void printTree(Node root) {
int maxLevel = getMaxTreeDepth(root);
printSubtree(Collections.singletonList(root), 1, maxLevel);
}
// Helper method to print each level of the binary tree
private static void printSubtree(List<Node> nodes, int level, int maxLevel) {
if (nodes.isEmpty() || isAllElementsNull(nodes))
return;
int floor = maxLevel - level;
int edgeLines = (int) Math.pow(2, Math.max(floor - 1, 0));
int firstSpaces = (int) Math.pow(2, floor) - 1;
int betweenSpaces = (int) Math.pow(2, floor + 1) - 1;
printWhitespaces(firstSpaces);
List<Node> newNodes = new ArrayList<>();
for (Node node : nodes) {
if (node != null) {
System.out.print(node.val);
newNodes.add(node.left);
newNodes.add(node.right);
} else {
System.out.print(" ");
newNodes.add(null);
newNodes.add(null);
}
printWhitespaces(betweenSpaces);
}
System.out.println();
for (int i = 1; i <= edgeLines; i++) {
for (int j = 0; j < nodes.size(); j++) {
printWhitespaces(firstSpaces - i);
if (nodes.get(j) == null) {
printWhitespaces(2 * edgeLines + i + 1);
continue;
}
if (nodes.get(j).left != null)
System.out.print("/");
else
printWhitespaces(1);
printWhitespaces(i * 2 - 1);
if (nodes.get(j).right != null)
System.out.print("\\");
else
printWhitespaces(1);
printWhitespaces(2 * edgeLines - i);
}
System.out.println();
}
printSubtree(newNodes, level + 1, maxLevel);
}
// Helper method to print whitespaces
private static void printWhitespaces(int count) {
for (int i = 0; i < count; i++)
System.out.print(" ");
}
// Helper method to check if all elements in a list are null
private static boolean isAllElementsNull(List<Node> list) {
for (Node node : list) {
if (node != null)
return false;
}
return true;
}
// Method to print the maximum sum path in a binary tree
public static void printMaxSumPath(Node root) {
List<Integer> path = new ArrayList<>();
List<List<Integer>> allPaths = new ArrayList<>();
int maxSum = Integer.MIN_VALUE;
calculateMaxSumPath(root, path, allPaths, maxSum);
// Find the path with maximum sum
List<Integer> maxPath = new ArrayList<>();
for (List<Integer> p : allPaths) {
int sum = p.stream().mapToInt(Integer::intValue).sum();
if (sum > maxSum) {
maxSum = sum;
maxPath = p;
}
}
// Print the path with maximum sum
System.out.print("Maximum Sum Path: ");
for (int i = 0; i < maxPath.size(); i++) {
System.out.print(maxPath.get(i));
if (i != maxPath.size() - 1) {
System.out.print(" -> ");
}
}
System.out.println("; Max Sum = " + maxSum);
}
// Helper method to calculate all possible paths and their sum
private static void calculateMaxSumPath(Node root, List<Integer> path, List<List<Integer>> allPaths, int maxSum) {
if (root == null) {
return;
}
path.add(root.val);
if (root.left == null && root.right == null) {
allPaths.add(new ArrayList<>(path));
} else {
calculateMaxSumPath(root.left, path, allPaths, maxSum);
calculateMaxSumPath(root.right, path, allPaths, maxSum);
}
path.remove(path.size() - 1);
}
// Method to get the maximum depth of a binary tree
private static int getMaxTreeDepth(Node node) {
if (node == null)
return 0;
return 1 + Math.max(getMaxTreeDepth(node.left), getMaxTreeDepth(node.right));
}
public static void main(String[] args) {
// Construct a binary tree with random numbers
Node root = new Node(10);
root.left = new Node(-2);
root.right = new Node(7);
root.left.left = new Node(8);
root.left.right = new Node(-4);
// Print the binary tree and the maximum sum path in the binary tree
printTree(root);
printMaxSumPath(root);
}
}
=====================================================
10
/ \
/ \
-2 7
/ \
8 -4
Maximum Sum Path: 10 -> 7; Max Sum = 17
Process finished with exit code 0