是否是平衡的二叉树 解题思路:

在理解题意以后,我们需要先分解下问题。首先要先获取节点高度,然后再再进行比对判断,判断每一个节点左右子树的高度差的绝对值是否超过1。

我们需要了解如何遍历二叉树,这样才能知道树的高度。还要了解递归的思想可以让代码逻辑更加清晰。

type TreeNode struct {
    left *TreeNode
    right *TreeNode
    value int
}

func max(a,b int) int {
    if a > b {
        return a
    }
    return b
}
func abs(a int) int {
    if a >= 0 {
        return a
    }
    return -a
}
func getHeight(root *TreeNode) int {
    if root == nil {
        return 0
    }
    return 1 + max(getHeight(root.left),getHeight(root.right))
}
func isBalanced(root *TreeNode) bool {
    if root == nil {
        return true
    }
    if abs(getHeight(root.left)-getHeight(root.right)) > 1 {
        return false
    }
    return isBalaned(root.left) && isBalaned(root.right)
}

  

原文地址:https://studygolang.com/articles/29553#reply0