題目：輸入一棵二叉樹的根結(jié)點，判斷該樹是不是平衡二叉樹。如果某二叉樹中任意結(jié)點的左右子樹的深度相差不超過1，那么它就是一棵平衡二叉樹。例如，下圖中的二叉樹就是一棵平衡二叉樹.

二叉平衡樹.jpg

最簡單的解法是遍歷每個節(jié)點左右節(jié)點深度，進行對比:
<pre><code>`
func isBalanceTree(rootNode:TreeNode?) -> Bool {
if rootNode == nil {
return true
}
let leftDepth:Int = treeMaxDepth(rootNode: rootNode?.leftChild)
let rightDepth:Int = treeMaxDepth(rootNode: rootNode?.rightChild)

    let diff:Int = leftDepth - rightDepth
    if diff > 1 || diff < -1 {
        return false
    }
    return isBalanceTree(rootNode: rootNode?.leftChild) && isBalanceTree(rootNode: rootNode?.rightChild)
}
`</code></pre>

上述解法不夠高效，我們可以每次遍歷的時候記錄一下深度:
<pre><code>`

func isBalanceTreeOnce(rootNode:TreeNode?,depth:inout Int) -> Bool {
    if rootNode == nil {
        depth = 0
        return true
    }
    var leftDepth:Int = 0
    var rightDepth:Int = 0
    if isBalanceTreeOnce(rootNode: rootNode?.leftChild, depth: &leftDepth) && isBalanceTreeOnce(rootNode: rootNode?.rightChild, depth: &rightDepth) {
        let diff:Int = leftDepth - rightDepth
        if diff <= 1 && diff >= -1 {
            depth = leftDepth > rightDepth ? leftDepth + 1 : rightDepth + 1
            return true
        }
    }
    return false
}

func isBalancedTree(rootNode:TreeNode?) -> Bool {
    var depth:Int = 0
    return isBalanceTreeOnce(rootNode: rootNode, depth: &depth)
}`</code></pre>

測試代碼:
<pre><code>`
var isBalance:Bool = binaryTreePath.isBalanceTree(rootNode: preRootNode)
print("FlyElephant-(depthData)二叉平衡樹--(isBalance)")

var isBalance2:Bool = binaryTreePath.isBalancedTree(rootNode: preRootNode)
print("FlyElephant-(depthData)二叉平衡樹--(isBalance2)")`</code></pre>