코딩 테스트 이론 - 백트래킹 (Backtracking)

백트래킹은

기본적으로 Tree..

DFS의 Preorder Traversal (전위 순회: Root → Left → Right)로 풀이 가능

 

https://hyunkookim.tistory.com/365

BST 이진 검색 트리(height, Depth, DFS 검색 방법: inorder, preorder, postorder)

 

class TreeNode:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None

def canReachLeaf(root):
    if not root or root.val == 0:
        return False
    
    if not root.left and not root.right:
        return True
    if canReachLeaf(root.left):
        return True
    if canReachLeaf(root.right):
        return True
    return False

def leafPath(root, path):
    if not root or root.val == 0:
        return False
    path.append(root.val)

    if not root.left and not root.right:
        return True
    if leafPath(root.left, path):
        return True
    if leafPath(root.right, path):
        return True
    path.pop()
    return False

 

참고 강의

https://youtu.be/Ar40zcPoKEI?si=ANrQRht6S-ERkYOl

 

https://youtu.be/atTzqxbt4DM?si=OTMYb-8eRMltSgTO

 

 

https://www.geeksforgeeks.org/find-paths-given-source-destination/

Print all paths from a given source to a destination - GeeksforGeeks