Skip to main content

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.

예제 입출력​

img

Input: root = [1,2,3,4,5]
Output: 3
Explanation: 3 is the length of the path [4,2,1,3] or [5,2,1,3].
참고

You can read the full description here.

풀이 1​

접근법​

  1. 한 개의 노드에 대해서, 왼쪽 서브 트리의 깊이와 오른쪽 서브 트리의 깊이를 합하면 그 노드를 거쳐가는 최대 직경이 나오는 것을 이용합니다.
  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
class Solution:
    def diameterOfBinaryTree(self, root: Optional[TreeNode]) -> int:
        left, right = 0, 0
        diameter = 0

        def getDepth(root: Optional[TreeNode], curDepth: int, isLeft: bool):
                nonlocal left, right
                if root == None:
                    return

                else:
                    if isLeft:
                        left = max(curDepth, left)
                        getDepth(root.left, curDepth + 1, True)
                        getDepth(root.right, curDepth + 1, True)
                    else:
                        right = max(curDepth, right)
                        getDepth(root.left, curDepth + 1, False)
                        getDepth(root.right, curDepth + 1, False)
                return

        def diameterOfSubTree(root: Optional[TreeNode]):
            nonlocal diameter, left, right
            left, right = 0, 0

            if root == None:
                return
            else:
                if root.left != None:
                    getDepth(root.left, 1, True)
                if root.right != None:
                    getDepth(root.right, 1, False)
                diameter = max(diameter, left + right)
                return

        def preorder(root: Optional[TreeNode]):
            if root == None:
                return
            diameterOfSubTree(root)
            if root.left != None:
                preorder(root.left)
            if root.right != None:
                preorder(root.right)
            return

        if root == None:
            return 0
        else:
            preorder(root)

        return diameter

복잡도 분석​

  • nn: 노드의 수
  • 시간복잡도: O(n2)O(n^2)

책에 있는 풀이​

참고

원본 코드는 여기에서 확인하실 수 있습니다.

풀이 2​

접근법​

  1. 풀이 1은 전위 순회에 가깝게 진행되는데, 루트 - 왼쪽 자식 - 오른쪽 자식으로 순회할 때 루트에서 깊이를 연산하는 부분이 반복되어 시간이 오래 걸립니다.
  2. DFS 풀이는 후위 순회입니다. 풀이 2에서는 리프 노드로부터의 거리를 상태값으로 가져가서 깊이를 여러 번 구하지 않아도 됩니다.
  3. dfs 함수는 상태값을 리턴하고, 상태값 기반으로 최대 경로를 갱신합니다.

image

구현 코드​

# Definition for a binary tree node.
class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None


class Solution:
    longest: int = 0

    def diameterOfBinaryTree(self, root: TreeNode) -> int:
        def dfs(node: TreeNode) -> int:
            if not node:
                return -1
            # 왼쪽, 오른쪽 각각 리프 노드까지 탐색
            left = dfs(node.left)
            right = dfs(node.right)

            # 가장 긴 경로
            self.longest = max(self.longest, left + right + 2)
            # 상태값
            return max(left, right) + 1

        dfs(root)
        return self.longest

복잡도 분석​

  • nn: 노드의 수
  • 시간복잡도: O(n)O(n)