1315-kir3i.md

1315. Sum of Nodes with Even-Valued Grandparent

Solution

• 시간복잡도: O(N)

• 알고리즘

  BFS, DFS

• 풀이설명

  일반적인 트리 탐색 문제지만 스택에 넣을 때 정보를 하나 더 저장했습니다. 부모 노드가 짝수인지 여부를 저장하는 isParentEven입니다. 부모 노드가 짝수인 경우 자식 노드가 존재할 때 자식 노드의 val을 ans에 합하도록 하면서 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):
        ans = 0

        #DFS
        s = [(root, False)]
        while s:
            curr, isParentEven = s.pop()

            if curr.left:
                s.append((curr.left, curr.val % 2 == 0))
                if isParentEven:
                    ans += curr.left.val
            if curr.right:
                s.append((curr.right, curr.val % 2 == 0))
                if isParentEven:
                    ans += curr.right.val
        return ans