问题定义
如果我们把二叉树看成一个图，父子节点之间的连线看成是双向的，我们姑且定义"距离"为两节点之间边的个数。写一个程序求一棵二叉树中相距最远的两个节点之间的距离。
image
书上的解法
书中对这个问题的分析是很清楚的，我尝试用自己的方式简短覆述。
计算一个二叉树的最大距离有两个情况:
- 情况A: 路径经过左子树的最深节点，通过根节点，再到右子树的最深节点。
- 情况B: 路径不穿过根节点，而是左子树或右子树的最大距离路径，取其大者。
只需要计算这两个情况的路径距离，并取其大者，就是该二叉树的最大距离。
image
type node struct {
data int
left *node
ritht *node
}
type result struct {
nMaxDepth int
nMaxDistance int
}
//情况A对应的数据
var p9 = &node{9, nil, nil}
var p8 = &node{8, nil, nil}
var p7 = &node{7, nil, nil}
var p6 = &node{6, nil, p9}
var p5 = &node{5, nil, nil}
var p4 = &node{4, p8, nil}
var p3 = &node{3, p6, p7}
var p2 = &node{2, p4, p5}
var p1 = &node{1, p2, p3}
//情况B对应的数据
var n6 = &node{6, nil, nil}
var n5 = &node{5, nil, nil}
var n4 = &node{4, nil, n6}
var n3 = &node{3, n5, nil}
var n2 = &node{2, n3, n4}
var n1 = &node{1, n2, nil}
func getMaxDistance(p *node) result {
if p == nil {
return result{-1, -1} //因为如果只有一个节点的时候，nMaxDepth是0(-1+1)，nMaxDistance也是0(-1+-1+2)
}
l := getMaxDistance(p.left)
r := getMaxDistance(p.ritht)
res := result{}
res.nMaxDepth = max(l.nMaxDepth, r.nMaxDepth) + 1
res.nMaxDistance = max(max(l.nMaxDistance, r.nMaxDistance), l.nMaxDepth+r.nMaxDepth+2)
return res
}
func max(a, b int) int {
if a > b {
return a
}
return b
}
func main() {
res1 := getMaxDistance(p1)
fmt.Println(res1.nMaxDepth, res1.nMaxDistance)
res2 := getMaxDistance(n1)
fmt.Println(res2.nMaxDepth, res2.nMaxDistance)
}
运行结果：
C:\Users\minping\Desktop>go run 1.go
3 6
3 4
result中的nMaxDepth很简单，就是max(left depth, rightdepth) +1 (这也是为什么初始值是result{-1, -1}的原因)
result中的nMaxDistance就比较复杂一点，是l.nMaxDistance, r.nMaxDistance(对应B情况,在左子树或者右子树中，不跨根节点)和l.nMaxDepth+r.nMaxDepth+2(对应A情况，跨根节点)三者的最大值。仔细想一想为什么是加2(因为根节点和左右子树通过两条边连接起来的，所以+2)
