[leetcode 2024/02/19] 543. Diameter of Binary Tree

https://leetcode.com/problems/diameter-of-binary-tree/description/

LeetCode - The World's Leading Online Programming Learning Platform

 

1. 접근 방법

트리의 가장 긴 지름을 구하는 문제이다.

 

우선 self.max_diameter를 선언을 해주어, 최대 length마다 값을 바꾸도록 하였다.

 

이후 노드를 기준으로, 왼쪽 노드의 최대 깊이(left_depth)와, 오른쪽 노드(right_depth)의 최대 깊이를 구해주었다.

 

구한 left_depth + right_depth 를 self.max_diameter와 비교해서 self.max_diameter에 값을 저장해 주었다.

 

이후 현재 있는 나의 노드는 또 부모 노드의 왼쪽 또는 오른쪽 노드로 사용되기 때문에, 

return 1 + max(left_depth, right_depth)를 통해 부모 노드에게 긴 depth를 전달해 주었다.

 

2. 코드

# 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
import math

class Solution:
    def diameterOfBinaryTree(self, root: Optional[TreeNode]) -> int:
        self.max_diameter = 0
        def depth(node):
            if not node:
                return 0
            left_depth = depth(node.left)
            right_depth = depth(node.right)
        
            self.max_diameter = max(self.max_diameter, left_depth + right_depth)
            return 1 + max(left_depth, right_depth)

        depth(root)
        return self.max_diameter

 

--- 아래에는 조금 더 시간이 많이 걸린 코드이다. ---

# 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
import math

class Solution:
    def diameterOfBinaryTree(self, root: Optional[TreeNode]) -> int:
        max_length_list = []
        total = []
        def left_node(node, length, max_length):
            if not node:
                max_length.append(length)
                return max_length
            left_node(node.left, length + 1, max_length)
            left_node(node.right, length + 1, max_length)
        

        def every_node(node):
            if not node:
                return
            max_length_list = []
            left_node(node.left, 0, max_length_list)
            left = max(max_length_list)
            max_length_list = []
            left_node(node.right, 0, max_length_list)
            right = max(max_length_list)
            total.append(left+right)
            every_node(node.left)
            every_node(node.right)

        every_node(root)
        return max(total)