Kotlin Leetcode - 110. Balanced Binary Tree

題目連接

/**
 * Example:
 * var ti = TreeNode(5)
 * var v = ti.`val`
 * Definition for a binary tree node.
 * class TreeNode(var `val`: Int) {
 *     var left: TreeNode? = null
 *     var right: TreeNode? = null
 * }
 */
class Solution {
    fun isBalanced(root: TreeNode?): Boolean {
        
    }
}

解題思路

這一題考的是對樹的處理

我們只要對樹的高度進行計算

就可以比較出這棵樹是不是符合 height-balanced 的條件

height-balanced 的條件有三個：

• 左邊的高度和右邊的高度，差異在 1 以內
• 左邊的子樹符合 height-balanced 的條件
• 右邊的子樹符合 height-balanced 的條件

要計算樹的高度，可以使用遞迴：

• 如果樹的 node 是 null，則此數的高度為 0
• 如果不是，則高度是左邊的高度或右邊的高度，看哪邊的高度更高，再加一

Kotlin 參考解答

/**
 * Example:
 * var ti = TreeNode(5)
 * var v = ti.`val`
 * Definition for a binary tree node.
 * class TreeNode(var `val`: Int) {
 *     var left: TreeNode? = null
 *     var right: TreeNode? = null
 * }
 */
class Solution {
    fun isBalanced(root: TreeNode?): Boolean = when {
        root == null -> true
        else -> Math.abs( depth(root.right) - depth(root.left) ) <= 1
             && isBalanced(root.left)
             && isBalanced(root.right)
    }

    fun depth(root: TreeNode?): Int = when {
        root == null -> 0
        else -> maxOf(depth(root.right), depth(root.left)) + 1
    }
}

---

• 回到 leetcode 列表
• 回到 Grind 75 列表