二叉樹上節(jié)點(diǎn)間的最大距離

從二叉樹的節(jié)點(diǎn)A出發(fā)，可以向上或者向下走，但沿途的節(jié)點(diǎn)只能經(jīng)過一次，當(dāng)?shù)竭_(dá)節(jié)點(diǎn)B時(shí)，路徑上的節(jié)點(diǎn)數(shù)叫做A到B的距離

比如，下圖所示的二叉樹，節(jié)點(diǎn)4和節(jié)點(diǎn)2的距離為2，節(jié)點(diǎn)5和節(jié)點(diǎn)6的距離為5，給定一棵二叉樹的頭節(jié)點(diǎn)head，求整棵樹上節(jié)點(diǎn)如啟棚間的最大距離

1

2　　　　　　　3

4　　 5 6 7

如果二叉樹的節(jié)點(diǎn)數(shù)為N，時(shí)間復(fù)雜度要求為O(N)

最大距離來自三種情況
1、h左子樹渣則上的最大距離
2、h右子樹上的最大距離
3、h左子樹上離h.left最遠(yuǎn)的距離旁塌（左子樹高度）+h右子樹上離h.right最遠(yuǎn)的距離（右子樹高度）+1