二叉树两个节点之间的最大距离

题目

给定一个二叉树，求它两个节点之间的最大距离。

比如二叉树：

    1
   / \
  2   3
 / \
4   5

的最大距离为 3。

分析

刚看到这个题目时有点懵，仔细分析了一下，求根节点为 Root 的二叉树中两个节点的最大距离，需要分两种情况考虑：

情况一

如果最大距离经过了 Root，则最大距离：

MaxDistance(root) = MaxDepth(root.Left) + MaxDepth(root.Right) + 2

假设 root 节点为 1，示例图为：

    1
  // \\
  2   3
// \
4   5

情况二

如果最大距离没有经过 Root，则最大距离：

MaxDistance(root) = max(MaxDistance(root.Left), MaxDistance(root.Right))

假设 root 节点为 1，示例图为：

      1
     /
    2
  // \\
  3   4
//     \\
5       6

想必大家已经通过公式看出规律来了，父节点的 maxDistance 可以通过两个子节点的 maxDistance 和 maxDepth 求出，合并 1 2 两种情况，最终的状态转移方程如下：

MaxDistance(root) = max(max(MaxDistance(root.Left), MaxDistance(root.Right)), MaxDepth(root.Left) + MaxDepth(root.Right) + 2)

实现

我们需要有个数据结构保存中间结果，即 maxDepth 和 maxDistance。

另外，这里我们确定 root 节点的深度为 0，因此将 nil 节点的深度初始化为 -1。

整个算法使用了递归方式。

type TreeNode struct {
    Val   int
    Left  *TreeNode
    Right *TreeNode
}

type result struct {
    maxDepth    int
    maxDistance int
}

func getMaxDistance(root *TreeNode) *result {
    if root == nil {
        return &result{
            maxDepth:    -1,
            maxDistance: 0,
        }
    }

    left := getMaxDistance(root.Left)
    right := getMaxDistance(root.Right)
    maxDepth := max(left.maxDepth+1, right.maxDepth+1)
    maxDistance := max(max(left.maxDistance, right.maxDistance), left.maxDepth+right.maxDepth+2)
    return &result{
        maxDepth:    maxDepth,
        maxDistance: maxDistance,
    }
}

func GetMaxDistance(root *TreeNode) int {
    result := getMaxDistance(root)
    return result.maxDistance
}

可以在这里在线运行：https://play.golang.org/p/CwIvHaBJwP-