Solution to problem 543 “Diameter of Binary Tree” from LeetCode.

Problem Statement

Given a binary tree, your task is to calculate the diameter of the tree. The diameter of a binary tree is the length of the longest path between any two nodes in the tree. This path may or may not pass through the root. The diameter is the number of edges.

Example:

          1
         / \
        2   3
       / \
      4   5

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

Solution

Depth-First Search

We go recursively. In the current node, we check for children. If there are children – we run the function recursively for the children. If there are no children – we return one. When we’ve gone through the children (in the current node) – we compare the maximum path and the sum of the depths of the children (replace the value of the maximum path if necessary). Return the value of the maximum path plus 1.

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
var m = 0
func diameterOfBinaryTree(root *TreeNode) int {
    m =0
    d(root)
    return m


}

func d(root *TreeNode) int {
    if root == nil {
        return 0
    }
    if root.Left == nil && root.Right == nil {
        return 1
    }
    l:=0
    r:=0
    if root.Left != nil {
        l = d(root.Left)
    }
    if root.Right != nil {
        r = d(root.Right)
    }
    if m<l+r{
        m = l+r
    }
    if l>r {
        return l+1
    }
    return r+1
}