[python3] 1448. Count Good Nodes in Binary Tree

풀이 일자: 22.09.01

난이도: [Medium]

분류: [Binary Tree/DFS]

문제 내용

주어진 Tree를 가지고 level이 올라가면서 지나온 경로의 node값보다 현재 node값이 큰 node의 갯수를 세는 문제였다. 한마디로 아래로 내려가면서 오름차순을 지키는 값을 가지는 노드 수를 물어보는 문제였다.

 

문제 해결 흐름

1. 일단 Tree이고 요소의 값을 확인을 해야하니까 Tree순회가 필요하겠는데.. DFS와 BFS중 어떤 것이 좋을까?

→ 아래로 내려가면서 루트로부터 자신의 경로 이전까지의 수보다 큰지를 확인해야하니까 DFS가 이 문제에 적합하겠네!

2. 현재의 값이 경로에 있는 수들과의 대소 비교가 필요하겠다

→ 해당 경로에서 큰 수를 보관을 해서 계속해서 파라미터로 넘겨주는 것이 필요하겠다.

 

# 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:
    ans = 0
    def goodNodes(self, root: TreeNode, prevMax = -10001) -> int:
        if root:
            if root.val >= prevMax:
                self.ans +=1
                prevMax = root.val
                print(root.val)
            self.goodNodes(root.left, prevMax)
            self.goodNodes(root.right, prevMax)
        return self.ans

다른 해결 방식

1. Python에서 DFS를 구현하는데 사용하는 다른 방식을 사용해보자.

→ DFS를 구현하기 위해 stack을 사용하는 방식과 deque를 사용하는 방식이 존재하는데 deque의 Time complexity가 더 유리하기에  deque를 이용하여 구현해보자.

# 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 goodNodes(self, root: TreeNode) -> int:
    	ans = 0
        dq = deque()
        dq.append((root, -inf))
        
        while dq:
        	node, maxval = dq.popleft()
            if node.val >= maxval:
            	ans += 1
            if node.left:
            	dq.append((node.left, max(node.val,maxval))
            if node.right:
            	dq.append((node.right, max(node.val,maxval))
       	return ans

문제 링크

https://leetcode.com/problems/count-good-nodes-in-binary-tree/