LeetCode 543. Diameter of Binary Tree

题目描述

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

样例

给定二叉树
      1
     / \
    2   3
   / \     
  4   5    
返回 3, 它是路径 [4,2,1,3] 或者 [5,2,1,3] 的长度。

算法

(递归遍历) O(n)
递归函数的返回值定义为从当前结点到叶子结点的最大长度，当前结点为空返回 0。
递归时，分别得到左右子树递归的返回值，则可以更新答案 depth。

时间复杂度

每个结点最多仅被遍历一次，故时间复杂度为 O(n)。

python code

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def __init__(self):
        self.depth = 0

    def dfs(self, root):
        if not root: return 0
        l = self.dfs(root.left)
        r = self.dfs(root.right)
        if self.depth < l + r:
            self.depth = l + r
        if l > r:
            return l + 1
        else:
            return r + 1

    def diameterOfBinaryTree(self, root: TreeNode) -> int:
        self.dfs(root)
        return self.depth