Balanced Binary Tree -- LeetCode

 
這道題是樹操作的題目，還是老套路用遞歸。這道題是求解樹是否平衡，還是有一些小技巧的。要判斷樹是否平衡，根據題目的定義，深度是比需的信息，所以我們必須維護深度，另一方面我們又要返回是否為平衡樹，那麼對於左右子樹深度差的判斷也是必要的。這裡我們用一個整數來做返回值，而0或者正數用來表示樹的深度，而-1則用來比較此樹已經不平衡了，如果已經不平衡，則遞歸一直返回-1即可，也沒有繼續比較的必要了，否則就利用返回的深度信息看看左右子樹是不是違反平衡條件，如果違反返回-1，否則返回左右子樹深度大的加一作為自己的深度即可。算法的時間是一次樹的遍歷O(n)，空間是棧高度O(logn)。代碼如下：

public boolean isBalanced(TreeNode root)
{
    return helper(root)>=0;
}
private int helper(TreeNode root)
{
    if(root == null)
        return 0;
    int left = helper(root.left);
    int right = helper(root.right);
    if(left<0 || right<0)
        return -1;
    if(Math.abs(left-right)>=2)
        return -1;
    return Math.max(left,right)+1;
}