解題思路
一條路徑的長度為該路徑經(jīng)過的節(jié)點數(shù)減一，所以求直徑（即求路徑長度的最大值）等效于求路徑經(jīng)過節(jié)點數(shù)的最大值減一间螟。而任意一條路徑均可以被看作由某個節(jié)點為起點赞警，從其左子樹和右子樹向下遍歷的路徑拼接得到验辞。假設我們知道對于該節(jié)點的左子樹向下遍歷經(jīng)過最多的節(jié)點數(shù) L （即左子樹的深度） 和其右子樹向下遍歷經(jīng)過最多的節(jié)點數(shù) R （即右子樹的深度）抄课，那么以該節(jié)點為起點的路徑經(jīng)過節(jié)點數(shù)的最大值即為 L+R+1 唱星。記節(jié)點 node 為起點的路徑經(jīng)過節(jié)點數(shù)的最大值為d_node雳旅，那么二叉樹的直徑就是所有節(jié)點d_node的最大值減一。
這可以通過遞歸算法來實現(xiàn)间聊，首先定義一個遞歸函數(shù)depth(node)攒盈，返回該節(jié)點為根的子樹的深度，先遞歸調(diào)用左子樹哎榴，得到左子樹深度為L型豁，再遞歸調(diào)用右子樹，得到右子樹深度為R叹话，則該節(jié)點為根的子樹的深度為 max(L, R) + 1偷遗。該節(jié)點的d_note值為 L + R + 1。
遞歸搜索每個節(jié)點驼壶，并設置一個全局變量記錄d_note的最大值，最后用 d_note - 1 就是最終結(jié)果喉酌。
步驟：
1)首先創(chuàng)建一個全局變量ans热凹，用來記錄d_note，并設初值為1泪电；
2)定義遞歸函數(shù)：
2.1)遞歸結(jié)束條件為訪問到空節(jié)點般妙，返回0；
2.2)遞歸訪問左子樹相速，得到左子樹深度 L碟渺；
2.3)遞歸訪問右子樹，得到右子樹深度 R突诬；
2.4)計算該節(jié)點為起點的路徑經(jīng)過節(jié)點數(shù)的最大值苫拍，即 L+R+1，并更新全局變量ans旺隙；
2.5)返回該節(jié)點為根的子樹的深度绒极，即 max(L, R) + 1；
3)對根節(jié)點進行遞歸蔬捷，返回 ans - 1垄提。
復雜度分析：
時間復雜度：O(N)，其中 N 為二叉樹的節(jié)點數(shù)周拐，即遍歷一棵二叉樹的時間復雜度铡俐，每個結(jié)點只被訪問一次。
空間復雜度：O(Height)妥粟，其中 Height 為二叉樹的高度审丘。由于遞歸函數(shù)在遞歸過程中需要為每一層遞歸函數(shù)分配棧空間罕容，所以這里需要額外的空間且該空間取決于遞歸的深度备恤，而遞歸的深度顯然為二叉樹的高度稿饰，并且每次遞歸調(diào)用的函數(shù)里又只用了常數(shù)個變量，所以所需空間復雜度為 O(Height) 露泊。
代碼
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def diameterOfBinaryTree(self, root: TreeNode) -> int:
self.ans = 1
def depth(node):
# 訪問到空節(jié)點了喉镰，返回0
if not node: return 0
# 左兒子為根的子樹的深度
L = depth(node.left)
# 右兒子為根的子樹的深度
R = depth(node.right)
# 計算d_node即L+R+1 并更新ans
self.ans = max(self.ans, L+R+1)
# 返回該節(jié)點為根的子樹的深度
return max(L, R) + 1
depth(root)
return self.ans - 1
