543. 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 thelongestpath between any two nodes in a tree. This path may or may not pass through the root.
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].
- Need two paths, a open path from the left and right and a closed path from the left and right
# Definition for a binary tree node. # class TreeNode(object): # def __init__(self, x): # self.val = x # self.left = None # self.right = None class Solution(object): def diameterOfBinaryTree(self, root): """ :type root: TreeNode :rtype: int """ def helper(root): if not root: return (0 , 0) left = helper(root.left) right = helper(root.right) return (max(left, right) + 1 , max(left + right + 1, max(left, right))) # (node numbers of open path , node numbers of of closed path) if not root: return 0 return helper(root) - 1 # for node number > 0, path = node -1