現在、二分探索木全体の最大不均衡を返す再帰的な方法をコーディングしています。私は再帰プログラミングに非常に慣れていないので、頭を包み込むのは非常に困難です。私が構築したツリーには 1 の不均衡がありますが、私のメソッドは 0 しか返しません。ここでの私のロジックには欠陥があると確信しています。
メソッドのすべてのステップで " (root == null){ return 0;} " が実行されていることは 100% 確信しています。私はそれを削除してさらに定義しようとしましたが、同じことを続けています。
これは私の現在の方法です：
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;
}