LeetCode 풀기 - 1315. Sum of Nodes with Even-Valued Grandparent

1315. Sum of Nodes with Even-Valued Grandparent

https://leetcode.com/problems/sum-of-nodes-with-even-valued-grandparent/

Sum of Nodes with Even-Valued Grandparent - LeetCode

문제)

솔루션1) - stack and tree traversal

이진 트리를 순회합니다.

재귀적 순회 시 부모의 노드를 계속 넘겨줍니다. 

부모 노드의 정보는 스택 자료구조에 저장합니다.

재귀 함수를 빠져 나올때는 스택에서 최상단(부모 노드)를 제거합니다.

# 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 sumEvenGrandparent(self, root: TreeNode) -> int:
        stack = []
        res = []
        
        def preorder(node, parent):
            if node is None:
                return
        
            # 부모 노드를 스택에 추가
            stack.append(parent)
                        
            if len(stack) >= 2:                
                grand_parent = stack[-2]
                if grand_parent and grand_parent.val % 2 == 0:
                    res.append(node.val)
            
            # 왼쪽 자식 방문
            preorder(node.left, node)
            # 오른쪽 자식 방문
            preorder(node.right, node)
            
            # 최상위 부모 제거
            stack.pop()
            
        preorder(root, None)
    
        return sum(res)

솔루션2) -DFS

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 sumEvenGrandparent(self, root: TreeNode) -> int:        
        res = []
        
        def dfs(node, p, gp):
            if node is None:
                return
        
            if gp and gp.val % 2 == 0:
                res.append(node.val)
        
            dfs(node.left, node, p)
            dfs(node.right, node, p)
            
        dfs(root, None, None)
        return sum(res)