leetcode250.집계 동수 서브트리

1228 단어 leetcode

1. 제목 설명


두 갈래 나무를 정해서 이 두 갈래 나무의 수치가 같은 하위 나무의 개수를 통계한다.
동수 트리는 이 트리의 모든 노드가 같은 수치를 가지고 있다는 것을 가리킨다.
예:
입력: root = [5,1,5,5,null,5]
              5             /\            1   5           /\    \          5   5   5

2. 문제풀이 사고방식


두 갈래 나무의 뒷순서를 따라 좌우 나무의 값이 현재 나무 뿌리 노드 값과 같는지 판단하고 결과를 이전 층으로 되돌려줍니다

3. 코드 구현

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    def __init__(self):
        self.count = 0
    def dfs(self, root):
        if not root:
            return True
        l = self.dfs(root.left)
        r = self.dfs(root.right)
        cur = True
        if root.left and root.val != root.left.val:
            cur = False
        if root.right and root.val != root.right.val:
            cur = False
        if l and r and cur:
            self.count += 1
        return l and r and cur
    def countUnivalSubtrees(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """
        self.dfs(root)
        return self.count

좋은 웹페이지 즐겨찾기