[LeetCode] 872 | Leaf-Similar Trees | Python

---

문제 링크: https://leetcode.com/problems/leaf-similar-trees/description/

---

문제

Consider all the leaves of a binary tree, from left to right order, the values of those leaves form a leaf value sequence.

For example, in the given tree above, the leaf value sequence is (6, 7, 4, 9, 8).

Two binary trees are considered leaf-similar if their leaf value sequence is the same.

Return true if and only if the two given trees with head nodes root1 and root2 are leaf-similar.

---

조건

• The number of nodes in each tree will be in the range [1, 200].
• Both of the given trees will have values in the range [0, 200].

---

내 풀이

DFS처럼 어떤 tree가 주어졌을 때 그 트리의 leaf를 찾는 함수를 짠다.

root1과 root2를 모두 그 함수를 돌려서 각각의 leaf1, leaf2를 구한 후, leaf1과 leaf2가 같으면 True, 다르면 False를 리턴한다.

---

코드

# 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 leafSimilar(self, root1: Optional[TreeNode], root2: Optional[TreeNode]) -> bool:
        leaf1, leaf2 = [], []

        def get_leaves(root, leaf):
            if not root:
                return 

            if root.left:
                get_leaves(root.left, leaf)
            if root.right:
                get_leaves(root.right, leaf)
            if not root.left and not root.right:
                leaf.append(root.val)

        get_leaves(root1, leaf1)
        get_leaves(root2, leaf2)

        return True if leaf1 == leaf2 else False