树的直径

树

说明

每个节点合并左右子树高度；所有节点中的最大路径长度即直径，时间 O(n)。

分析

每个节点返回本子树的高度，同时用左高度加右高度更新穿过当前节点的路径长度。所有节点的候选路径取最大值，就是以边数计的直径。

空树高度0，叶高1；根左右高度各1，候选路径边数为1+1=2。返回给父节点的是max(左高,右高)+1，和候选路径含义不同。必须在每个节点更新答案，因为最长路径未必经过全树根。

查看图表代码

适用前提与边界

一次后序遍历即可完成；空树直径为零。 直径按边数计算，单节点与空树都返回0；极深树需要注意递归栈开销。

示例输入与调用

root := &Node{Left: &Node{}, Right: &Node{}}
	fmt.Println(Diameter(root))

运行输出

2

完整 Go 示例

package main

import "fmt"

type Node struct{ Left, Right *Node }

func Diameter(root *Node) int {
	best := 0
	var height func(*Node) int
	height = func(n *Node) int {
		if n == nil {
			return 0
		}
		l, r := height(n.Left), height(n.Right)
		if l+r > best {
			best = l + r
		}
		if l > r {
			return l + 1
		}
		return r + 1
	}
	height(root)
	return best
}

func main() {
	root := &Node{Left: &Node{}, Right: &Node{}}
	fmt.Println(Diameter(root))
}