题解 | #二叉树的直径#

题目分析

1. 题目给出我们一棵树的根节点
2. 题目要求我们返回这棵树的最大的直径，其中直径定义为，树上任意两个叶子节点路径长度的最大值

方法一：（双重递归）递归确定深度+递归确定直径

• 实现思路
  • 我们用两个递归函数来得到最终的最长直径结果
  • 递归函数一depth
    • 目标：获取当前节点的深度
    • 返回条件：当前节点为空None时返回深度为0
    • 递归主体：递归左子树获取其深度l，递归右子树获取其高度r，因此当前节点的深度为max(l,r)+1
  • 递归函数二diameterOfBinaryTree

    • 目标：获得当前节点为根的树中最大直径

    • 返回条件：当前节点为空None时返回树中最大直径为0

    • 递归主体：根据左子树右子树深度来确定通过当前节点的路径最大直径为d，返回d, 递归左子树的结果，递归右子树的结果三者中最大的值为最终目标

# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param root TreeNode类 
# @return int整型
#
class Solution:
    def depth(self, node):
        if not node:
            return 0
        l = self.depth(node.left)            # 左子树的深度
        r = self.depth(node.right)           # 右子树的深度
        return max(l,r) + 1                  # 当前节点的深度
        
    def diameterOfBinaryTree(self , root: TreeNode) -> int:
        # write code here
        if not root:
            return 0
        d = self.depth(root.left) + self.depth(root.right)    # 通过当前节点本身的直径
        return max(d, self.diameterOfBinaryTree(root.left), self.diameterOfBinaryTree(root.right)) # 返回三者之一 

复杂度分析

• 时间复杂度：$O(n^2)O(n^2)$，其中$nn$是树中节点数量。对于某个节点，算法在计算直径时访问一次节点，并且同时要访问其对应的整棵子树来计算高度，子树中所有的节点又被访问了一次，因此最终代价为平方级别的
• 空间复杂度：$O(height)O(height)$，其中$heightheight$是树的高度，递归深度和树高成线性关系

方法二：递归深度+直径实时记录

• 实现思路
  • 根据方法一，我们只保留递归计算树中节点深度的递归函数。
  • 在每次计算出来当前节点的深度时，我们同时拿到了其左子树和右子树的深度
  • 此时就已经可以计算通过当前节点所对应的直径长度了，我们将其存储在ans中
  • 最终返回ans即可

# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param root TreeNode类 
# @return int整型
#
class Solution:
    def diameterOfBinaryTree(self , root: TreeNode) -> int:
        # write code here
        self.ans = 0								# 最终结果
        def depth(node):
            if node == None:
                return 0
            l = depth(node.left)					# 左子树深度
            r = depth(node.right)					# 右子树深度
            self.ans = max(self.ans, l + r)			# 记录直径最大值
            return max(l, r) + 1					# 返回深度
        
        depth(root)
        return self.ans

复杂度分析

• 时间复杂度：$O(n)O(n)$，所有的节点都被遍历一次，因此时间代价和节点数量呈线性关系
• 空间复杂度：$O(height)O(height)$，其中$heightheight$为树高，递归深度和树高呈线性关系