树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