計算二叉搜索樹的最大不平衡

Question

我目前正在編碼一個遞歸方法來返回整個二叉搜索樹的最大不平衡。我對遞歸編程非常陌生，所以很難把我的頭圍繞起來。 我建立的樹有1的不平衡，但我的方法只返回0.我敢肯定我的邏輯是有缺陷的。

我100％確定它在該方法的每一步中都運行「（root == 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; 

} 

Answer 1

在你的代碼的邏輯似乎是錯誤的：一個節點的最大不平衡不是其子女的最大不平衡的總和。相反，最大不平衡應該是它的孩子（ren）高度差異的絕對值（如果其中一個是空的，那麼該節點的最大不平衡量就是0，所以當前節點的最大不平衡完全取決於它的唯一的孩子）。