题解 | #二叉树的直径#

二叉树的直径

http://www.nowcoder.com/practice/15f977cedc5a4ffa8f03a3433d18650d

题目分析

题目给出我们一棵树的根节点

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

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

实现思路
- 我们用两个递归函数来得到最终的最长直径结果
- 递归函数一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})$ ，其中 $n$ 是树中节点数量。对于某个节点，算法在计算直径时访问一次节点，并且同时要访问其对应的整棵子树来计算高度，子树中所有的节点又被访问了一次，因此最终代价为平方级别的
空间复杂度： $O (h e i g h t)$ ，其中 $h e i g h t$ 是树的高度，递归深度和树高成线性关系

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

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

alt

# 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