求大神解釋543. Diameter of Binary Tree

腦子很笨，想不明白為什麼別人寫的答案會compare left subtree and right subtree. 為啥要+1。

原貼： https://stackoverflow.com/questi...er-of-a-binary-tree

請各位請教！謝過。

每一层你找left 和right最大的值，也就是每边subtree的最大diamter。
当你返回上一层的时候你返回它们最大的值，

+自己本身

加 一就是root 它自己本身  你想的一个root 左右两个结点。就是 3

ymsfnm4l 发表于 2019-3-22 11:40
两种做法

第一种

我也有个问题想请教下，对于这两种方法，一般是鼓励用全局变量然后同级单独写一个function再recursion呢，还是直接在原来function里写个sub function然后recursion?

我比较倾向于定义global variable然后单独写function，但是之前有次面试问面试官可不可以这样做，他说Python最好不要定义global variable，有人知道为什么吗？

ymsfnm4l 发表于 2019-3-23 01:39
第一种做法绝对没错.

第二种办法算投机取巧, 是竞赛里常用的. 这种做法其实并不好, 正经工作里是不鼓 ...

老哥你说的很有道理 但是可以把头像换一下么？

ymsfnm4l 发表于 2019-3-23 01:39
第一种做法绝对没错.

第二种办法算投机取巧, 是竞赛里常用的. 这种做法其实并不好, 正经工作里是不鼓 ...

多谢解答！我当时主要是不明白面试官为什么不让用global variable，可能特定情况或者考察我特定解题方法吧233

楼主注意，那个链接的讨论的解法都是通过求树的高度depth，辅助计算树的diameter，而在求高度的时候，根节点高度为1，所以递归公式是1+max(depth(left substree),depth(right sub tree))