ほぼ日刊競プロ leetcode　543. Diameter of Binary Tree

543. Diameter of Binary Tree

Given the root of a binary tree, return 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.
The length of a path between two nodes is represented by the number of edges between them.

考えたこと

二分木の直径を求める問題．直径とは二分木の中で一番最長の距離である．
考えた方としては再帰的に左へ行った場合と右へ行った場合の長距離を覚えておき．最長距離をどんどん更新していく．

# 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:
       ans = [0]
       #行きがけ法
       def preorder(root,ans):
           if not root:
               return 0
           #左と右の最大値の深さを求める
           L = preorder(root.left,ans)
           R = preorder(root.right,ans)
           ans.append(max(L+R,max(ans)))
           
           return 1+max(L,R)
       preorder(root,ans)
       return max(ans)