题目:二叉平衡树表示树中的任意一个结点，其两棵子树的高度不超过1，判断一棵树是不是二叉平衡树.

二叉平衡树.jpg

解法一

直接递归遍历每个结点的左右节点，比较差值，如果符合条件，继续比较，否则直接返回.
<pre><code>` func treeNodeHeight(treeNode:TreeNode?) -> Int {
if treeNode == nil {
return 0
}

    return max(treeNodeHeight(treeNode:treeNode?.leftChild), treeNodeHeight(treeNode: treeNode?.rightChild)) + 1
}

func isBalanced(root:TreeNode?) -> Bool {
    
    if root == nil {
        return true
    }
    
    let heightDiff:Int = abs(treeNodeHeight(treeNode: root?.leftChild) - treeNodeHeight(treeNode: root?.rightChild))
    
    if heightDiff > 1 {
        return false
    } else {
        return isBalanced(root:root?.leftChild) && isBalanced(root:root?.rightChild)
    }
    
}`</code></pre>

解法二

递归最大的问题大于多次重复计算，因此将每次计算的结果保存结果，解法一中获取高度同时还可以计算是否是平衡树，对解法一进行改进如下:
<pre><code>` func checkTreeNodeHeight(treeNode:TreeNode?) -> Int {
if treeNode == nil {
return 0
}

    // 检查左子树是否平衡
    let leftHeight:Int = checkTreeNodeHeight(treeNode: treeNode?.leftChild)
    if leftHeight == -1 {
        return -1
    }
    
    let rightHeight:Int = checkTreeNodeHeight(treeNode: treeNode?.rightChild)
    
    if rightHeight == -1 {
        return -1
    }
    
    let heightDiff:Int = abs(leftHeight - rightHeight)
    if heightDiff > 1 {
        return -1
    } else {
        return max(leftHeight, rightHeight) + 1
    }
    
}


func isBalanced2(root:TreeNode?) -> Bool {
    if checkTreeNodeHeight(treeNode: root) == -1 {
        return false
    } else {
        return true
    }
}`</code></pre>

测试结果:
<pre><code>`var binaryTree:BinarTree = BinarTree()
var isBalanced:Bool = binaryTree.isBalanced(root: preOrderRoot)
if isBalanced {
print("FlyElephant---是二叉平衡树")
} else {
print("FlyElehant---不是二叉平衡树")
}

var isBalanced2:Bool = binaryTree.isBalanced2(root: preOrderRoot)
if isBalanced2 {
print("FlyElephant---是二叉平衡树")
} else {
print("FlyElehant---不是二叉平衡树")
}`</code></pre>

FlyElephant.png