'''
Description: 
Autor: Au3C2
Date: 2021-03-23 16:53:05
LastEditors: Au3C2
LastEditTime: 2021-03-23 17:00:26
'''
class Solution:
    def diameterOfBinaryTree(self, root: TreeNode) -> int:
        self.ans = 1
        def depth(node):
            # 访问到空节点了，返回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)
            # 返回该节点为根的子树的深度
            return max(L, R) + 1

        depth(root)
        return self.ans - 1

# 树，简单。哪里简单了啊
# 建议和 0124 一起看
# https://leetcode-cn.com/problems/diameter-of-binary-tree/