leetcode543. 二叉树的直径
给定一棵二叉树，你需要计算它的直径长度。一棵二叉树的直径长度是任意两个结点路径长度中的最大值。这条路径可能穿过也可能不穿过根结点。
示例 :
给定二叉树
1
/ \
2 3
/ \
4 5
返回 3, 它的长度是路径 [4,2,1,3] 或者 [5,2,1,3]。
思路整理：
一、直接递归
1、最大节点数：左节点深度+右节点深度+1，最多边数：L+R
2、不断遍历，左右节点
但注意：递归搜索每个节点并设一个全局变量记录最大值
递归代码：
（1）求直径（2）直径L+R\左子树的直径\右子树的直径的最大值
二、利用全局变量记录最大值
代码如下：
class Solution:
def diameterOfBinaryTree(self, root: TreeNode) -> int:
if not root:
return 0
def depth(root):
if not root:
return 0
left=depth(root.left)
right=depth(root.right)
return max(left,right)+1
left=depth(root.left)
right=depth(root.right)
ld=self.diameterOfBinaryTree(root.left)
rd=self.diameterOfBinaryTree(root.right)
tmp=max(rd,ld)
return max(left+right,tmp)
代码如下：
class Solution:
def diameterOfBinaryTree(self, root: TreeNode) -> int:
if not root:
return 0
self.ans=1
def depth(root):
if not root:
return 0
left=depth(root.left)
right=depth(root.right)
self.ans=max(self.ans,left+right+1)
return max(left,right)+1
depth(root)
return self.ans-1
-20200104
