求一棵二叉树中相距最远的两个节点之间的距离

问题定义

如果我们把二叉树看成一个图，父子节点之间的连线看成是双向的，我们姑且定义"距离"为两节点之间边的个数。写一个程序求一棵二叉树中相距最远的两个节点之间的距离。

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)

参考