二叉树的直径

1. 题目描述

给定一棵二叉树，你需要计算它的直径长度。一棵二叉树的直径长度是任意两个结点路径长度中的最大值。这条路径可能穿过也可能不穿过根结点。

2. 思路

1. 思路一
   • 二叉树的直径可以看作经过的节点数-1
   • 经过的节点数则可以用1+左子树的深度+右子树的深度计算
   • 深度可以用DFS的先序版本

3. 实现

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func diameterOfBinaryTree(root *TreeNode) int {
    maxVal := 0
    dfs(root, &maxVal)
    return maxVal
}

func dfs(root *TreeNode, maxVal *int) {
    if root == nil {
        return
    }

    leftHeight := getHeight(root.Left)
    rightHeight := getHeight(root.Right)

    *maxVal = max(*maxVal, leftHeight + rightHeight)
    dfs(root.Left, maxVal)
    dfs(root.Right, maxVal)

}

func getHeight(root *TreeNode) int {
    if root == nil {
        return 0
    }
    return 1 + max(getHeight(root.Left), getHeight(root.Right))
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

4. 参考

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