LeetCode 543. Diameter of Binary Tree - Python

LeetCode 543. Diameter of Binary Tree - Python

 

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.

 

이진트리의 지름 구하기 즉 가장 긴 path의 '길이'를 구하면 된다.

이 때, 노드 사이의 길이란 노드 사이의 edge의 개수이다. 

예를 들어 아래의 경우 path [4,2,1,3] 나 [5,2,1,3]가 가장 길기 때문에 3이 반환된다.

 

 

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.

 

Solution 1:

class Solution(object):
    def diameterOfBinaryTree(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """
        self.ans = 0
        
        def depth(p):
            if not p: return 0
            left, right = depth(p.left), depth(p.right)
            self.ans = max(self.ans, left+right)
            return 1 + max(left, right)
            
        depth(root)
        return self.ans

 

Solution 2:

# 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):
        """
        :type root: TreeNode
        :rtype: int
        """
        def dfs(node):
            if node is None:
                return 0
            left = dfs(node.left)
            right = dfs(node.right)
            self.ans = max(self.ans, left+right+1)
            return max(left, right)+1
        self.ans = 1
        dfs(root)
        return self.ans-1

(참고 사이트)

솔루션 출처: https://leetcode.com/problems/diameter-of-binary-tree/discuss/101145/Simple-Python

[알고리즘] 깊이 우선 탐색(DFS) : https://gmlwjd9405.github.io/2018/08/14/algorithm-dfs.html

인스턴스 변수: http://pythonstudy.xyz/python/article/19-%ED%81%B4%EB%9E%98%EC%8A%A4

*클래스 정의에서 메서드 안에서 사용되면서 "self.변수명"처럼 사용되는 변수를 인스턴스 변수(instance variable)라 하는데, 이는 각 객체별로 서로 다른 값을 갖는 변수이다.