【LeetCode】【Kotlin】 110. Balanced Binary Tree

AVL Tree

又稱高度平衡樹。任一節點的左右子樹高度差須為-1、0或1。

👉資料結構與演算法：AVL Tree

題意

此二元樹是否高度平衡? (return true 或 false).

方法一 : 針對每一個節點判斷左右子樹是否平衡(每節點都重新計算一次左右子樹高度)

class Solution {
    fun countNodeHight(node : TreeNode?): Int{
        if (node == null) return -1
        return max(countNodeHight(node.left), countNodeHight(node.right)) + 1
    }

    fun isBalanced(root: TreeNode?): Boolean {
        if (root == null) return true
        val leftHight = countNodeHight(root.left)
        val rightHight = countNodeHight(root.right)

        return abs(leftHight - rightHight) <= 1 && isBalanced(root.left) && isBalanced(root.right)

    }
}

方法二 : 只做一次計算，在計算過程中順便判斷是否平衡

使用 -4 代表不平衡。

class Solution {
    fun countNodeHight(node : TreeNode?): Int{
        if (node == null) return -1

        val leftHight = countNodeHight(node.left)
        if (leftHight == -4) return -4
        val rightHight = countNodeHight(node.right)
        if (rightHight == -4) return -4

        if (abs(leftHight - rightHight) > 1) return -4

        return max(countNodeHight(node.left), countNodeHight(node.right)) + 1
    }

    fun isBalanced(root: TreeNode?): Boolean {
        if (root == null) return true

        return countNodeHight(root) != -4
    }
}