【leetcode 5418.二叉木における偽回文経路】Python解題構想

タイトルリンク:
解題構想:dfsツリーの経路がリーフノードに達する場合,経路中の異なるノードの個数が奇数の数字が1個を超えないか否かを判断する必要がある.(再帰に入る前の操作->cnt[root.val]+=1と再帰に出た後の操作->cnt[root.val]-=1を重点的に体得し、dong兄のアルゴリズムの写しを見に行かなければならない.

# 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 pseudoPalindromicPaths (self, root: TreeNode) -> int:
        def pando(array):           
            odd=0
            for i in array:
                if i%2==1:
                    odd+=1
            if odd<=1:
                return True
            else:
                return False

        ans=0
        def dfs(root,cnt):
            nonlocal ans
            if not root.left and not root.right:
                cnt[root.val]+=1
                if pando(cnt):
                    ans+=1
                cnt[root.val]-=1
            else:
                cnt[root.val]+=1
                if root.left:
                    dfs(root.left,cnt)
                if root.right:
                    dfs(root.right,cnt)
                cnt[root.val]-=1
        cnt=[0]*10
        dfs(root,cnt)
        return ans