DFS: 100. Same Tree

100. Same Tree

 

# 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 getElemets(self, node, stack):
        if not node:
            return stack.append('null')
        
        stack.append(node.val)

        self.getElemets(node.left, stack)
        self.getElemets(node.right, stack)
        return stack
        
    def isSameTree(self, p: Optional[TreeNode], q: Optional[TreeNode]) -> bool:
        lstack = self.getElemets(p, [])
        rstack = self.getElemets(q, [])
        print(lstack)
        print(rstack)
        return lstack == rstack

 

https://youtu.be/vRbbcKXCxOw?si=b186VE9JKkUeDcn9

 

DFS 는 재귀로 풀자!

 

# 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 isSameTree(self, p: Optional[TreeNode], q: Optional[TreeNode]) -> bool:
        # 둘다 null 이면, 둘다 같이 마지막 노드까지 왔으면 같은 트리 구조
        if not p and not q: 
            return True

        # 둘중 하나만 null 이거나, 두개의 값이 다르면
        if (not p or not q) or (p.val != q.val): 
            return False

        # 여기까지 오면, p, q 둘다 null 이 아니고, val 도 같음
        # 왼쪽, 오른쪽 둘다 참이면 True, 아니면 False
        return (self.isSameTree(p.left, q.left) and
                self.isSameTree(p.right, q.right))

 

내 코드보다 훨씬 빠름

 

dfs로,,,,좌우 둘다 비교 하면서,

• 둘다 null 이면 true
• 둘중 하나만 null 이면 false
• 두개 값이 다르면 false
• 두개 하위 트리 비교해서 둘다 같으면 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 isSameTree(self, p: Optional[TreeNode], q: Optional[TreeNode]) -> bool:
        
        def dfs(node1, node2):
            # 큐 사용은 bfs, 재귀나 스텍 사용은 dfs
            if not node1 and not node2: # 둘다 null 이면 같으니깐
                return True

            if not node1 or not node2: # 한쪽만 null 인 경우
                return False

            if node1.val != node2.val: # 현재 노드 값이 다른 경우
                return False

            # 왼쪽, 오른쪽 서브트리 비교 해서 둘다 같으면 
            return dfs(node1.left, node2.left) and dfs(node1.right, node2.right)

        return dfs(p, q)

 

BFS와 DFS의 차이

BFS (Breadth-First Search):
탐색 순서: 같은 레벨의 모든 노드를 먼저 탐색한 후, 다음 레벨로 넘어갑니다.
구현: 큐(Queue)를 사용.
용도: 최단 경로 탐색 등에 적합.

DFS (Depth-First Search):
탐색 순서: 한 방향으로 끝까지 탐색한 후, 돌아와서 다른 방향을 탐색합니다.
구현: 재귀(Recursion)나 스택(Stack)을 사용.
용도: 경로 탐색, 모든 경우의 수 탐색 등에 적합.