leetcode-543. 二叉树的直径

543. 二叉树的直径 - 力扣（Leetcode）

深度优先遍历，每个节点的直径等于左子树的最大深度加上右子树的最大深度，取一个最大值即可

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
var maxHeight int

func diameterOfBinaryTree(root *TreeNode) int {
    if root == nil {
        return 0
    }
    maxHeight = 0

    depth(root)

    return maxHeight
}

func depth(root *TreeNode) int {
    if root == nil {
        return 0
    }

    var left, right int
    if root.Left != nil {
        left = depth(root.Left) + 1
    }

    if root.Right != nil {
        right = depth(root.Right) + 1
    }

    if left + right > maxHeight {
        maxHeight = left+right
    }

    if left > right {
        return left
    }
    return right
}