Упражнения на Java: найдите длину самого длинного последовательного пути последовательности данного двоичного дерева
Java Basic: упражнение 184 с решением
Напишите программу на Java, чтобы найти длину самого длинного последовательного пути последовательности данного двоичного дерева.
Примечание: самый длинный последовательный путь должен быть от родителя к ребенку.
Образец бинарного дерева:
Результат:
Пример решения:
Java-код:
import java.util.*;
public class Solution {
public static void main(String[] args) {
TreeNode a = new TreeNode(1);
a.right = new TreeNode(3);
a.right.left = new TreeNode(2);
a.right.right = new TreeNode(4);
a.right.right.right = new TreeNode(5);
a.right.right.right.right = new TreeNode(6);
System.out.println("Length of the longest consecutive sequence path: "+longest_Consecutive(a));
}
public static int longest_Consecutive(TreeNode root) {
if (root == null) {
return 0;
}
int result = diffn(root, 1) + diffn(root, -1);
return Math.max(result, Math.max(longest_Consecutive(root.left), longest_Consecutive(root.right)));
}
private static int diffn(TreeNode tnode, int diff) {
if (tnode == null) {
return 0;
}
int left_depth = 0, right_depth = 0;
// check node
if (tnode.left != null && tnode.val - tnode.left.val == diff) {
left_depth = diffn(tnode.left, diff) + 1;
}
if (tnode.right != null && tnode.val - tnode.right.val == diff) {
right_depth = diffn(tnode.right, diff) + 1;
}
return Math.max(left_depth, right_depth);
}
}
Пример вывода:
Длина самой длинной последовательности последовательных путей: 4
Блок - схема:
Редактор кода Java:
Внесите свой код и комментарии через Disqus.
Предыдущий: Напишите Java-программу, принимающую положительное число, и многократно добавляйте все ее цифры, пока результат не будет иметь только одну цифру.
Далее: Напишите программу на Java, чтобы проверить, являются ли две данные строки изоморфными или нет.
Каков уровень сложности этого упражнения?
Новый контент: Composer: менеджер зависимостей для PHP , R программирования