kotlin 高效判断二叉树是否是平衡二叉树

平衡二叉树的最主要特征就是任意一个节点的左右子树高度相差不超过1
高效的判定方法主要以后续遍历的思想对二叉树进行判断，先判断子树是否平衡，然后判断这个节点的左右子树的高度差距是否超过1

data class BTreeNode(
    var left: BTreeNode? = null,
    var right: BTreeNode? = null,
    var value: Int = 0
)

fun main() {
    val tree = BTreeNode(
        BTreeNode(
            BTreeNode(BTreeNode(), BTreeNode()), BTreeNode(BTreeNode(), BTreeNode())
        ),
        BTreeNode(
            BTreeNode(BTreeNode(BTreeNode()), BTreeNode()), BTreeNode(BTreeNode(), BTreeNode())
        )
    )
    val array = intArrayOf(0)
    println("${isBalance(tree, array)} array[0] = ${array[0]}")
}

fun isBalance(tree: BTreeNode?, array: IntArray): Boolean {
    if (tree == null) {
        return true
    }

    val arrayTempL = intArrayOf(0)
    val arrayTempR = intArrayOf(0)
    // 先判断左右子树平衡，若子树不平衡就不用向上判断了
    if (isBalance(tree.left, arrayTempL) && isBalance(tree.right, arrayTempR)) {
        // 判断本节点是否平衡
        val diff = arrayTempL[0] - arrayTempR[0]
        println("diff = $diff")
        if (diff in -1..1) {
            array[0] = max(arrayTempL[0], arrayTempR[0]) + 1
            return true
        }
        return false
    }
    return false
}
复制代码