543. Diameter of Binary Tree

Stanislav Gumeniuk включен в leetcode leetcode-problem

2020.05.17 270 слов Пару мгновений

Содержание

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

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

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

пример:

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

Решение

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

Идем рекурсивно. В текущем узле проверяем наличии детей. если дети есть – запускаем функцию рекусивно для детей. Если детей нет – возвращаем единицу. когда обошли детей ( в текущем узле ) – сравниваем максимальный путь и сумму глубин детей ( заменяем если надо значение максимального пути ). Возвращаем значение максимального пути плюс 1.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40


/**
 * 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
}