Решение задачи 543 “Diameter of Binary Tree” с LeetCode.

Условие задачи

Дано бинарное дерево, Ваша задача посчитать диаметр дерева. Диаметр бинарного дереве – это длина длиннейшего пути между двумя узлами дерева. Этот путь может как и проходить через корень, так и не проходить. Диаметр – это кол-во рёбер.

пример:

          1
         / \
        2   3
       / \     
      4   5    

Вернуть 3,что является длиной пути через узлы [4,2,1,3] или [5,2,1,3].

Решение

Поиск в глубину

Идем рекурсивно. В текущем узле проверяем наличии детей. если дети есть – запускаем функцию рекусивно для детей. Если детей нет – возвращаем единицу. когда обошли детей ( в текущем узле ) – сравниваем максимальный путь и сумму глубин детей ( заменяем если надо значение максимального пути ). Возвращаем значение максимального пути плюс 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
}