Given a binary tree, you need to compute the length of the diameter of the tree. The diameter of a binary tree is the length of the longest path between any two nodes in a tree. This path may or may not pass through the root.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24 | # Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def height(self, root: TreeNode) -> int:
if root is None:
return 0
else:
return 1+max(self.height(root.left),self.height(root.right))
def diameterOfBinaryTree(self, root: TreeNode) -> int:
if root is None:
return 0
else:
lheight = self.height(root.left)
rheight = self.height(root.right)
ldiam = self.diameterOfBinaryTree(root.left)
rdiam = self.diameterOfBinaryTree(root.right)
return max(lheight+rheight,ldiam,rdiam)
|
Like this post? Share on:
Twitter
❄ Facebook
❄ Email