모각코 1주차 dfs

def dfs(graph, start_node):
    visit = list()
    stack = list()

    stack.append(start_node)

    while stack:
        node = stack.pop()
        if node not in visit:
            visit.append(node)
            stack.extend(graph[node])
    return visit

dfs code - iterator

 

def dfs_recursive(graph, start, visit=None):
    if visit is None:
        visit = list()

    visit.append(start)

    for next in graph[start]:
        if next not in visit:
            dfs_recursive(graph, next, visit)
    return visit

dfs code - recursive

 

관련 문제 1

leetcode - Leaf_Similar Trees

https://leetcode.com/problems/leaf-similar-trees/description/?envType=study-plan-v2&envId=leetcode-75

Leaf-Similar Trees - LeetCode

풀이방법

간단한 dfs 구현 문제

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution(object):
    def leafSimilar(self, root1, root2):
        """
        :type root1: TreeNode
        :type root2: TreeNode
        :rtype: bool
        """
        def dfs(root, seq):
            if not root:
                return
            if not root.left and not root.right:
                seq.append(root.val)
            dfs(root.left, seq)
            dfs(root.right, seq)
        seq1, seq2 = list(), list()
        dfs(root1, seq1)
        dfs(root2, seq2)
        return seq1 == seq2

 

관련문제 2

1148 - Count Good Nodes in Binary Tree

Count Good Nodes in Binary Tree - LeetCode

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution(object):
    def goodNodes(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """
        def dfs(root, greater_num, cnt):
            if not root:
                return cnt
            if root.val >= greater_num:
                cnt+=1
                greater_num = root.val
            cnt = dfs(root.left, greater_num, cnt)
            cnt = dfs(root.right, greater_num, cnt)
            return cnt
        num = dfs(root, -10001, 0)
        return num

재귀 dfs 를 통해서 해결하였다.

문제는 별로 어렵지 않았다.

 

 

관련문제 3

437. Path Sum III

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution(object):
    def pathSum(self, root, targetSum):
        """
        :type root: TreeNode
        :type targetSum: int
        :rtype: int
        """
        self.numOfPaths = 0
        self.dfs(root, targetSum)
        return self.numOfPaths
    
    def dfs(self, node, target):
        if node is None:
            return 
        self.test(node, target)
        self.dfs(node.left, target)
        self.dfs(node.right, target)
        
    def test(self, node, target):
        if node is None:
            return
        if node.val == target:
            self.numOfPaths += 1
            
        self.test(node.left, target-node.val)
        self.test(node.right, target-node.val)