543.二叉树的直径

给定一棵二叉树，你需要计算它的直径长度。一棵二叉树的直径长度是任意两个结点路径长度中的最大值。这条路径可能穿过也可能不穿过根结点。

本题需要明确二叉树的直径计算方法：

• 二叉树的直径不一定过根节点,需要遍历左子节点和右子节点。
• root的直径 = 左子树深度+右子树的深度+1
• root的高度 = Max(左子树深度，右子树深度) + 1
  所以保存一个节点当前直径最大值，再递归的求每个节点左右子树的深度，每次递归都保存直径最大值，最后返回即可。

class Solution:
    def diameterOfBinaryTree(self, root: Optional[TreeNode]) -> int: 
        result=[]
        def getdepth(root):
            if not root:
                return 0
            left=getdepth(root.left)
            right=getdepth(root.right)
            result.append(left+right+1)
            return 1+max(left,right)
        getdepth(root)
        return max(result)-1

这里强调一波概念：

• 二叉树节点的深度：指从根节点到该节点的最长简单路径边的条数。
• 二叉树节点的高度：指从该节点到叶子节点的最长简单路径边的条数。
• 二叉树的直径, 相当于求其任意两个节点的最大路径, 这又可以转化为每个节点的左子树深度+右子树深度+1 。
• 但leetcode中强调的深度和高度很明显是按照节点来计算的，如图：