110. 平衡二叉树 👌

110. 平衡二叉树

1. 整个递归的终止条件。
2. 一级递归需要做什么？
3. 应该返回给上一级的返回值是什么？

因此，也就有了我们解递归题的三部曲：

1. 找整个递归的终止条件：递归应该在什么时候结束？
2. 找返回值：应该给上一级返回什么信息？
3. 本级递归应该做什么：在这一级递归中，应该完成什么任务？

一定要理解这3步，这就是以后递归秒杀算法题的依据和思路。

// 从上到下，递归，复用最大深度代码 
// 最坏时间On^2，平均时间Onlogn, 空间on
func isBalanced(root *TreeNode) bool {
    if root == nil {
        return true            //1，递归结束条件，父节点没有子节点了
    }
    if abs(maxDepth(root.Left) - maxDepth(root.Right)) > 1 {
        return false        //2，两个子树，高度差超过一，不符合
    }
    //3，继续递归，要把结构看成 只有三项构成=root+left+right
    return isBalanced(root.Left) && isBalanced(root.Right) 
}
//最大深度函数
func maxDepth(root *TreeNode) int {
    if root == nil {
        return 0
    }
    return max(maxDepth(root.Left), maxDepth(root.Right)) +1    //核心，从上到下，递归
}
//大小比较函数
func max(a,b int) int {
    if a>b {
        return a
    }
    return b
}
//绝对值函数
func abs(x int) int {
    if x < 0 {
       return -1 * x
    }
    return x
}

//也可调用自带的数学库，来实现比大小，不推荐
func isBalanced(root *TreeNode) bool {
    if root == nil {
        return true
    }
    if math.Abs(float64(maxDepth(root.Left)) - float64(maxDepth(root.Right))) > 1 {
        return false
    }
    return isBalanced(root.Left) && isBalanced(root.Right)
}

func maxDepth(root *TreeNode) int {
    if root == nil {
        return 0
    }

    return int(math.Max(float64(maxDepth(root.Left)), float64(maxDepth(root.Right))) +1)    
    //核心，从上到下，递归
}

方法二：自底向上的递归

方法一由于是自顶向下递归，因此对于同一个节点，函数 height 会被重复调用，导致时间复杂度较高。如果使用自底向上的做法，则对于每个节点，函数 height 只会被调用一次。
自底向上递归的做法类似于后序遍历，对于当前遍历到的节点，先递归地判断其左右子树是否平衡，再判断以当前节点为根的子树是否平衡。如果一棵子树是平衡的，则返回其高度（高度一定是非负整数），否则返回 −1。如果存在一棵子树不平衡，则整个二叉树一定不平衡。

//返回是否平衡,时空都是On
func isBalanced(root *TreeNode) bool {
    _, isBal := get_Depth_and_Balance(root)
    return isBal
}

//同时判断深度 和是否平衡，这题的真正考点
func get_Depth_and_Balance(root *TreeNode) (depth int, isBal bool) {   
    if root == nil {
        return 0, true
    }
    if root.Left == nil && root.Right == nil {
        return 1, true
    }
    Left_Depth, Left_IsBal := get_Depth_and_Balance(root.Left)
    Right_Depth, Right_IsBal := get_Depth_and_Balance(root.Right)
    depth = max(Left_Depth, Right_Depth) +1     //root就是一层，有子树，就是新的一层
    isBal = Left_IsBal && Right_IsBal && abs(Left_Depth - Right_Depth) <=1

    return depth, isBal

}

//大小比较函数
func max(a,b int) int {
    if a>b {
        return a
    }
    return b
}

//绝对值函数
func abs(x int) int {
    if x < 0 {
       return -1 * x
    }
    return x
}

//自底向上的递归，时空都是On的，因为不用重复遍历，判断子树平衡
func isBalanced(root *TreeNode) bool {
    return height(root) >= 0
}

func height(root *TreeNode) int {
    if root == nil {
        return 0
    }
    leftHeight := height(root.Left)
    rightHeight := height(root.Right)
    if leftHeight == -1 || rightHeight == -1 || abs(leftHeight - rightHeight) > 1 {
        return -1
    }
    return max(leftHeight, rightHeight) + 1
}

func max(x, y int) int {
    if x > y {
        return x
    }
    return y
}

func abs(x int) int {
    if x < 0 {
        return -1 * x
    }
    return x
}

复杂度分析

• 时间复杂度：O(n)，其中 n 是二叉树中的节点个数。使用自底向上的递归，每个节点的计算高度和判断是否平衡都只需要处理一次，最坏情况下需要遍历二叉树中的所有节点，
• 空间复杂度：O(n)，其中 n 是二叉树中的节点个数。空间复杂度主要取决于递归调用的层数，递归调用的层数不会超过 n。