872. Leaf-Similar Trees

문제)

872. Leaf-Similar Trees

 

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.

 

Example 1:

Input: root1 = [3,5,1,6,2,9,8,null,null,7,4], root2 = [3,5,1,6,7,4,2,null,null,null,null,null,null,9,8]
Output: true

Example 2:

Input: root1 = [1,2,3], root2 = [1,3,2]
Output: false

 

Constraints:

• 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].

 

 

솔루션1)

- dfs로 노드를 순회

- node의 왼쪽 자식과 오른쪽 자식이 없으면 leaf이므로 값을 리스트에 저장

class Solution:
    def leafSimilar(self, root1: Optional[TreeNode], root2: Optional[TreeNode]) -> bool:
        
        def dfs(node, leafs):
            if node is None:
                return
            
            if node.left is None and node.right is None:
                # leaf node
                leafs.append(node.val)
                return
            
            dfs(node.left, leafs)
            dfs(node.right, leafs)
            
        leafs1 = []
        dfs(root1, leafs1)
        
        leafs2 = []
        dfs(root2, leafs2)        
        
        return leafs1 == leafs2

솔루션2)

-  솔루션1의 코드를 조금 더 최적화 해서 dfs() 함수의 파라미터로 넘어가는 leaf 노드의 값을 저장하는 리스트 매개 변수를 제거

- 그런데, 솔루션1보다 속도는 더 느리네요...ㅠ

class Solution:
    def leafSimilar(self, root1: Optional[TreeNode], root2: Optional[TreeNode]) -> bool:
        def dfs(node):
            if node is None:
                return []
            if node.left is None and node.right is None:
                return [node.val]
            
            return dfs(node.left) + dfs(node.right)
        
        return dfs(root1) == dfs(root2)