[数据结构与算法]剑指 Offer 55 - II. 平衡二叉树

剑指 Offer 55 - II. 平衡二叉树

难度简单187

输入一棵二叉树的根节点，判断该树是不是平衡二叉树。如果某二叉树中任意节点的左右子树的深度相差不超过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

注意：本题与主站 110?题相同：https://leetcode-cn.com/problems/balanced-binary-tree/

思路：
此树的深度?等于?左子树的深度?与?右子树的深度?中的?最大值?+1
时间复杂度：O(NlogN)

空间复杂度：O(N)，最差情况下（树退化为链表时），系统递归需要使用?O(N)O(N)?的栈空间。

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func abs(a, b int) int {
	if a > b {
		return a-b
	}
	return b - a
}

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

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

	return max(depth(root.Left), depth(root.Right)) + 1 // 此树的深度 等于 左子树的深度 与 右子树的深度 中的 最大值 +1+1 
}

func isBalanced(root *TreeNode) bool {
	if root == nil {
		return true
	}

    // 高度差 <= 1 并且 左子树和右子树都是平衡的
	return abs(depth(root.Left), depth(root.Right)) <= 1 && isBalanced(root.Left) && isBalanced(root.Right)
}

?