Преобразовать отсортированный массив в двоичное дерево поиска с минимальной высотой
526 просмотра
1 ответ
Я хочу преобразовать отсортированный целочисленный массив в двоичное дерево поиска. Я разместил свой код ниже. То, что я не могу изобразить, это то, как рекурсия на самом деле работает с циклом for как вставка.
Так что, если мой массив [1,3,4, 5,8,10], я делаю 4, который является серединой массива, становится корнем моего BST, затем делаю цикл с начала массива и вставляю в дерево корень только что создан. Мой вопрос, почему порядок вставленных результатов не так, как отсортированный массив?
public TreeNode sortedArrayToBST(int[] A) {
if (A == null || A.length == 0){
return null;
}
TreeNode root = new TreeNode(findMid(A));
for (int i = 0; i < A.length; ++i){
insert(root, A[i]);
}
return root;
}
private int findMid(int[] A){
int left = 0;
int right = A.length -1;
int mid = A[left + (right - left)/2];
return mid;
}
private void insert (TreeNode root, int val){
if (root == null || root.val == val){
return;
}
if (val < root.val){
TreeNode left = new TreeNode(val);
root.left = left;
}
if (val > root.val){
TreeNode right = new TreeNode(val);
root.right = right;
}
insert(root.left,val);
insert(root.right,val);
}
Автор: wenjing li
Источник
Размещён: 13.11.2019 11:36
Ответы (1)
0 плюса
У вас есть пара проблем с вашим рекурсивным insert
методом. Во-первых, каждый раз, когда значение val
не равно значению корня, вы создаете новый узел. Это неверно, потому что, делая это, вы создаете несколько узлов и устанавливаете дочерний элемент корня на каждом шаге рекурсии для этих новых узлов, что является избыточным. Давайте рассмотрим ваш метод для каждого узла.
Добавление 4
4
Добавление 1
4
/
1
Добавление 3
4
/
3
На данный момент, мы можем точно определить ошибку. Почему левого ребенка 4 заменили на 3? Давайте рассмотрим ваш insert
метод, где root
находится узел со значением 4 и val
3.
- Первое условие if-оператора оценивается как ложное, поэтому перейдем к
- Второе условие if-оператора оценивается как true, поэтому создайте новый узел с
val
и установите root.left равным этому новому узлу - Третье условие if-оператора оценивается как ложное, поэтому продолжаем
- Рекурсивный вызов
insert(3.left, 3)
просто возвращается с3 == 3
- Рекурсивный вызов
insert(null, 3)
просто возвращается сroot == null
Так в чем же дело? Прекратите создавать новые узлы при каждом рекурсивном вызове в стеке вызовов. Хотите верьте, хотите нет, вы должны создавать новый узел только тогда, когда он root
равен нулю, потому что это означает, что вы прошли дерево до пустого дочернего элемента. Как насчет рекурсивных вызовов? Нет необходимости делать рекурсивный вызов для каждого из дочерних элементов root, потому что вы проходите только один путь обхода в BST. Вы поворачиваете налево или направо на каждом узле. Так что вы делаете только рекурсивный вызов в зависимости от значения val
относительно значения корня. Вот как это должно выглядеть,
private TreeNode insert (TreeNode root, int val){
if (root == null){
return new TreeNode(val);
}
if (val == root.val){
//if you don't want to add repeats in the tree, then
//add your own code to deal with that here
//although as it stands now, this code will not add repeats
}
if (val < root.val){
root.left = insert(root.left, val);
}
if (val > root.val){
root.right = insert(root.right, val);
}
return root;
}
Автор: Chris Gong
Размещён: 04.08.2016 08:09
Вопросы из категории :
- java В чем разница между int и Integer в Java и C #?
- java Как я могу определить IP моего маршрутизатора / шлюза в Java?
- java Каков наилучший способ проверки XML-файла по сравнению с XSD-файлом?
- java Как округлить результат целочисленного деления?
- java Преобразование списка <Integer> в список <String>
- java Почему я не могу объявить статические методы в интерфейсе?
- recursion Find number of files with a specific extension, in all subdirectories
- recursion Что такое хвостовая рекурсия?
- recursion Рекурсия или итерация?
- recursion Путь от рекурсии к итерации
- recursion Рекурсивный список файлов в CLI Linux с указанием пути относительно текущего каталога
- recursion Что такое оптимизация вызовов?
- binary-search-tree How do you validate a binary search tree?
- binary-search-tree Как сериализовать двоичное дерево
- binary-search-tree Почему std :: map реализована как красно-черное дерево?
- binary-search-tree Как реализовать двоичное дерево поиска в Python?
- binary-search-tree Куча против бинарного дерева поиска (BST)
- binary-search-tree PHP летнее время обнаружения