36 lines
1.1 KiB
Python
36 lines
1.1 KiB
Python
|
# 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 diameterOfBinaryTree(self, root: Optional[TreeNode]) -> int:
|
||
|
|
result = [0]
|
||
|
|
|
||
|
|
def dfs(node):
|
||
|
|
# Leaf node height will be 1
|
||
|
|
# Empty node height will be -1
|
||
|
|
|
||
|
|
if node is None: return -1
|
||
|
|
|
||
|
|
lefth = dfs(node.left)
|
||
|
|
righth = dfs(node.right)
|
||
|
|
|
||
|
|
# Diameter calc:
|
||
|
|
#
|
||
|
|
# Cause for current node will be pointing to both
|
||
|
|
# left and right nodes and we need to consider
|
||
|
|
# them (+2)
|
||
|
|
#
|
||
|
|
# e.g. consider this is leaf node, lefth and righth = -1
|
||
|
|
# so, current node's diameter should be 0 = 2 + -1 + -1
|
||
|
|
result[0] = max(result[0], 2 + lefth + righth)
|
||
|
|
|
||
|
|
# return max height including the node itself
|
||
|
|
return 1 + max(lefth, righth)
|
||
|
|
|
||
|
|
dfs(root)
|
||
|
|
|
||
|
|
return result[0]
|
||
|
|
|