树3 二叉树的直径
给定一棵二叉树，你需要计算它的直径长度。一棵二叉树的直径长度是任意两个结点路径长度中的最大值。这条路径可能穿过也可能不穿过根结点。
示例 :
给定二叉树
1
/ \
2 3
/ \
4 5
返回 3, 它的长度是路径 [4,2,1,3] 或者 [5,2,1,3]。
第一种思路：关键点：递归+二叉树深度
（1）递归的思路，比较左子树的直径，右子树的直径，和左子树的深度+右子树的深度
（2）定义二叉树深度
代码如下：
# 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:
if not root:
return 0
left=self.diameterOfBinaryTree(root.left)
right=self.diameterOfBinaryTree(root.right)
all1=maxdepth(root.left)+maxdepth(root.right)
return max(max(left,right),all1)
def maxdepth(root):
if not root:
return 0
else:
left=maxdepth(root.left)
right=maxdepth(root.right)
return max(left,right)+1
第二种思路：遍历+二叉树深度
代码如下：
class Solution:
def diameterOfBinaryTree(self, root: TreeNode) -> int:
if not root:
return 0
self.ans=0
def maxdepth(root):
if not root:
return 0
else:
left=maxdepth(root.left)
right=maxdepth(root.right)
self.ans=max(self.ans,left+right)
return max(left,right)+1
maxdepth(root)
return self.ans
