Diameter of Binary Tree

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.

Example: Given a binary tree 1 / \ 2 3 / \ 4 5

Return 3, which is the length of the path [4,2,1,3] or [5,2,1,3].

Note: The length of path between two nodes is represented by the number of edges between them.

Github: code.dennyzhang.com

Credits To: leetcode.com

Leave me comments, if you have better ways to solve.

## https://code.dennyzhang.com/diameter-of-binary-tree ## Basic Ideas: dfs ## Get the height of the subtree ## Complexity: Time O(n), Space O(1) # Definition for a binary tree node. # class TreeNode: # def __init__(self, x): # self.val = x # self.left = None # self.right = None class Solution: def diameterOfBinaryTree(self, root: TreeNode) -> int: res = 0 def getHeight(root): if not root: return 0 l = getHeight(root.left) r = getHeight(root.right) nonlocal res res = max(res, l+r) return max(l, r)+1 getHeight(root) return res