Kotlin Leetcode - 543. Diameter of 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 diameterOfBinaryTree(root: TreeNode?): Int {

    }
}

解題思路

這個題目處理樹的部分

我們可以使用遞迴的方式判斷樹的深度 diameter

• 如果節點為 null，樹的深度為 0
• 如果節點不為 null
  • 取得左邊的深度 left
  • 取得左邊的深度 right
  • 如果 left + right 比目前的 diameter 要深，換成 left + right
  • 回傳目前深度 max(left, right) + 1 給父節點計算用

Kotlin 參考解答

點擊展開解答

可以使用尾遞迴的方式撰寫

class Solution {
    fun diameterOfBinaryTree(root: TreeNode?): Int {
        var depth = 0

        tailrec fun search(node: TreeNode?): Int {
            node ?: return 0
            val left = search(node.left)
            val right = search(node.right)
            diameter = max(left + right, diameter)
            return 1 + max(left, right)
        }
        search(root)

        return depth
    }
}

---

• 回到 leetcode 列表