[LeetCode] 110. Balanced Binary Tree [Python(파이썬)]

'파이썬 알고리즘 인터뷰'를 보고 작성한 글입니다. 😀
문제 👉 <Balanced Binary Tree - LeetCode>

1. 문제 (균형 이진 트리)

이진 트리가 높이 균형(Height-Balanced)인지 판단하라.

높이 균형은 모든 노드의 서브 트리 간의 높이 차이가 1 이하인 것을 마한다.

2. 풀이

• 재귀탐색을 이용한 풀이

3. 코드

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

class Codec:

    def serialize(self, root):
        """Encodes a tree to a single string.

        :type root: TreeNode
        :rtype: str
        """

        q = collections.deque([root])
        result = []

        while q:
            node = q.popleft()
            if node:
                q.append(node.left)
                q.append(node.right)
                result.append(str(node.val))
            else:
                result.append('#') # null을 '#'으로 표현

        return ' '.join(result)



    def deserialize(self, data):
        """Decodes your encoded data to tree.

        :type data: str
        :rtype: TreeNode
        """

        if data == '#': return None

        nodes = data.split()

        root = TreeNode(int(nodes[0]))
        q = collections.deque([root])
        idx = 1

        while q:
            node = q.popleft()
            if nodes[idx] != '#':
                node.left = TreeNode(int(nodes[idx]))
                q.append(node.left)
            idx += 1

            if nodes[idx] != '#':
                node.right = TreeNode(int(nodes[idx]))
                q.append(node.right)
            idx += 1

        return root






# Your Codec object will be instantiated and called as such:
# ser = Codec()
# deser = Codec()
# ans = deser.deserialize(ser.serialize(root))

• 결과 :

방식	Status	Runtime	Memory	Language
재귀탐색	[Accepted]	44 ms	18.9 MB	python3

 

---

References

•  

---

🏋🏻 개인적으로 공부한 내용을 기록하고 있습니다.
잘못된 부분이 있다면 과감하게 지적해주세요!! 🏋