Leetcode 17th August

Leetcode 17th August

Count Good Nodes in Binary Tree

이 문제는 Tree 를 순회하면서 Node의 상태가 good인 node의 갯수를 리턴하는 문제입니다.
This is the Question return count of good node in tree

상태가 good 인 node란? tree의 parent의 값 들이 모두 자기 자신보다 작거나 같은 경우
What is the meaning of good node? the node’s value are greater than or equal to all of the values of parent node in tree

그래서 저는 dfs를 통해 Tree를 순회하면서 node의 parent의 값을 비교하는 방식으로 구현하였습니다.
So i use dfs algorithm for access node by tree, and then calculate this node is good or not. if the node is good node then i adding 1 in answer

Python

# 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:
        
        queue = deque()
        root.parent = None
        queue.append(root)
        ans = 0
        while len(queue):
            q = queue.popleft()
            if q.left:
                q.left.parent = q
                queue.append(q.left)
            if q.right:
                q.right.parent = q
                queue.append(q.right)
            # TODO: checking this queue is good or not
            parent = q.parent
            is_good = True
            while parent:
                if q.val < parent.val:
                    is_good = False
                    break
                parent = parent.parent
            if is_good:
                ans += 1
        return ans