HàPhan 河

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)
}
}
``````