В настоящее время я кодирую рекурсивный метод, чтобы вернуть максимальный дисбаланс на все двоичное дерево поиска. Я очень новичок в рекурсивном программировании, поэтому довольно сложно обернуть голову. Дерево, которое я построил, имеет дисбаланс 1, но мой метод возвращает 0. Я уверен, что моя логика здесь испорчена.Вычисление максимального дисбаланса дерева двоичного поиска
Я на 100% уверен, что его запуск «(корень == null) {return 0;}» на каждом шаге метода. Я попытался удалить его и определить его дальше, и он продолжает делать то же самое.
Это мой текущий метод:
public int getMaxImbalance(){
return Math.abs(getMaxImbalance(root));
}
public int getMaxImbalance (TreeNode<E> root){
if (root == null){
return 0;
}else if(root.left != null && root.right == null){
return 1 + getMaxImbalance(root.left) + getMaxImbalance(root.right);
//adds 1 left is true and right is false
}else if(root.left == null && root.right != null){
return -1 + getMaxImbalance(root.left) + getMaxImbalance(root.right);
//adds -1 left is false and right is true
}
return getMaxImbalance(root.left) + getMaxImbalance(root.right);
//calls itself if both fields are null;
}