Day 11 of 30 days Leetcode challenge

HàPQ -

Diameter of Binary Tree

Given a binary tree, you need to compute the length of the diameter of the tree. The diameter of a binary tree is the length of the longest path between any two nodes in a tree. This path may or may not pass through the root.

Example:
Given a binary tree

          1
         / \
        2   3
       / \     
      4   5

Return 3, which is the length of the path [4,2,1,3] or [5,2,1,3].

Note: The length of path between two nodes is represented by the number of edges between them.

Solution

Use DFS, with carrying the max value

class Solution {
    func diameterOfBinaryTree(_ root: TreeNode?) -> Int {
        var currentMax: Int = 0
        depthOfBinaryTree(root, &currentMax, 0)
        return currentMax
    }
    
    func depthOfBinaryTree(_ node: TreeNode?, _ currentMax: inout Int, _ currentDepth: Int) -> Int {
        if node == nil { return currentDepth }
        
        let leftDepth = depthOfBinaryTree(node?.left, &currentMax, currentDepth)
        let rightDepth = depthOfBinaryTree(node?.right, &currentMax, currentDepth)
        
        currentMax = max(currentMax, leftDepth + rightDepth)
        
        return max(leftDepth + 1, rightDepth + 1)
    }
}