[LeetCode 75] Easy - 872. Leaf-Similar Trees

872. Leaf-Similar Trees

 

내 풀이

# 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 getleaf(self, root):        
        leaf1 = []

        s1 = [(root, 1)] # node, depth
        max_depth = 1
        while s1:
            node, depth = s1.pop()
            max_depth = max(depth, max_depth)
            if not node.left and not node.right:
                leaf1.append(node.val)

            if node.left:
                s1.append((node.left, depth+1))
            if node.right:
                s1.append((node.right, depth+1))
        return leaf1

    def leafSimilar(self, root1: Optional[TreeNode], root2: Optional[TreeNode]) -> bool:
        l1 = self.getleaf(root1)
        l2 = self.getleaf(root2)

        return l1==l2

 

https://youtu.be/Nr8dbnL0_cM?si=f085POH61mw8nLdH

 

```
# 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:
        # DFS 로..
        def dfs(root, leaf):
            if not root:
                return
            if not root.left and not root.right:
                leaf.append(root.val)
                return
            
            dfs(root.left, leaf)
            dfs(root.right, leaf)

        leaf1, leaf2 = [], []
        dfs(root1, leaf1)
        dfs(root2, leaf2)

        return leaf1 == leaf2