题目：输入一棵二叉树的根结点，判断该树是不是平衡二叉树。如果某二叉树中任意结点的左右子树的深度相差不超过1，那么它就是一棵平衡二叉树。例如，下图中的二叉树就是一棵平衡二叉树.
二叉平衡树.jpg
最简单的解法是遍历每个节点左右节点深度，进行对比:
<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>
