Leetcode題解 Python：四月挑戰DAY11 Diameter of Binary Tree

給一串二元樹，問直徑，也就是節對節之間的最長距離。

如果以 root 來看，通過 root 的最長距離，就是 root.left 的最大深度加上 root.right 的最大深度。

於是方向很清晰，我們要用一個函數去取得該node的最大深度。這樣就能進而找出各個距離，再找出最長距離。


要寫遞迴函數，而且會從最深的地方開始，而最深的地方會往上層層回傳最大深度。

因此回傳的值是「深度」，如果沒有node，就回傳 0。

如果有node，要往上回傳最大深度，就需要知道 node.left 與 node.right 的深度，最大深度是從二者選著大的，然後加上自身 +1。

當我們得到 node.left 與 node.right 的深度時，兩者相加後，就能得到通過該 node 的最長距離。

這樣就能用 max() 去更新最大值，等待遞迴函數跑完，此時的最大值就是該二元樹的最長距離。

class Solution:
    def diameterOfBinaryTree(self, root: TreeNode) -> int:
        self.maxDM = 0        
        def getMaxDepth(node):
            if node:
                left_depth = getMaxDepth(node.left)
                right_depth = getMaxDepth(node.right)
                DM = left_depth + right_depth
                self.maxDM = max(self.maxDM, DM)
                return 1 + max(left_depth, right_depth)
            else:
                return 0
        getMaxDepth(root)
        return self.maxDM