55-II.平衡二叉树

一、 题目

输入一棵二叉树的根节点，判断该树是不是平衡二叉树。如果某二叉树中任意节点的左右子树的深度相差不超过1，那么它就是一棵平衡二叉树。 示例 1:

给定二叉树 [3,9,20,null,null,15,7]

     3
    / \
   9  20
     /  \
    15   7

返回 true 。

示例 2:

给定二叉树 [1,2,2,3,3,null,null,4,4]

        1
       / \
      2   2
     / \
    3   3
   / \
  4   4

返回 false 。

限制：

0 <= 树的结点个数 <= 10000

来源：力扣（LeetCode）

链接：https://leetcode-cn.com/problems/ping-heng-er-cha-shu-lcof

著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

二、 解法

深度有用到上一题的思路。

func isBalanced(_ root: TreeNode?) -> Bool {
    let deepL = maxDepth(root?.left)
    let deepR = maxDepth(root?.right)
    if (deepL == 0 && deepR == 0) {
        return true
    }
    if (abs(deepL - deepR) > 1) {
        return false
    }
    return (isBalanced(root?.left) && isBalanced(root?.right))
}

func maxDepth(_ root: TreeNode?) -> Int {
    var deep = 0
    guard let root = root else { return deep }
    var queue: [TreeNode] = [root]
    var currentLevelCount = 1
    var nextLevelCount = 0
    
    while queue.isEmpty == false {
        let current = queue.removeFirst()
        currentLevelCount -= 1
        
        if let left = current.left {
            queue.append(left)
            nextLevelCount += 1
        }
        
        if let right = current.right {
            queue.append(right)
            nextLevelCount += 1
        }
        
        if currentLevelCount == 0 {
            deep += 1
            currentLevelCount = nextLevelCount
            nextLevelCount = 0
        }
    }
    
    return deep
}