力扣链接:
https://leetcode-cn.com/probl...
解题思路:
- 均衡二叉树的定义:二叉树每个节点的左右两个子树的高度差的绝对值不超过 1
- 求二叉树的门路或者活深度的时候,应用的是前序遍历,而求高度的时候,应用的是后序遍历
- 递归求解三部曲:(1)确定参数:传入的参数就是节点,初始化就是根节点 (2)完结条件,当root == nil时返回的就是true (3)单层递归条件:后序遍历,先遍历左子树,再遍历右子树,最初解决根节点
// 应用递归的方法,求出左右子树,判断左右子树是否是均衡二叉树func isBalanced(root *TreeNode) bool { if root == nil { return true } // 别离递归判断左右子树是不是均衡二叉树 if !isBalanced(root.Left) || !isBalanced(root.Right) { return false } leftHigh := maxDepth(root.Left) + 1 rightHign := maxDepth(root.Right) + 1 if abs(leftHigh, rightHign) > 1 { return false } return true}func maxDepth(node *TreeNode) int { if node == nil { return 0 } left := maxDepth(node.Left) right := maxDepth(node.Right) return max(left, right) + 1}func max(a, b int) int { if a > b { return a } return b}func abs(x, y int) int { r := x - y if r < 0 { return -1 * r } return r}