python - 在这种情况下，如何摆脱递归函数的全局变量？

Question

我正在练习一些递归编码

          5
         / \
        1   5
       / \   \
      5   5   5

给定一棵二叉树，计算单值子树的数量。

单值子树意味着子树的所有节点都具有相同的值。

这是我想出的代码。但是，我必须把全局变量来计算单值的数量。我不知道如何摆脱它。这是我的代码。

def __init__(self):
    self.count = 0

def countUnivalSubtrees(self, root):
        def traverse(root):
            if not root:
                return {}

            count_left = traverse(root.left)
            count_right = traverse(root.right)

            for k, v in count_right.items():
                if k in count_left:
                    count_left[k] = count_left[k] + v
                else:
                    count_left[k] = v

            count_left[root.val] = count_left.get(root.val, 0) + 1
            if len(count_left.keys()) == 1:
                self.count += 1

            return count_left

        traverse(root)
        return self.count

Answer 1

这样的事情怎么样？

# returns (count_of_uni_value_subtrees, value)
# assumes nodes have a value other than None
def f(root, val):
  if not root:
    return (0, val)

  (left_count, left_val) = f(root.left, root.val)
  (right_count, right_val) = f(root.right, root.val)

  if left_val == root.val == right_val:
    return (1 + left_count + right_count, root.val)

  else:
    return (left_count + right_count, None)

"""
           f(5)
          /    \
        d(1)   e(5)
       /    \    \
      a(5)  b(5)  c(5)
"""

节点 a、b 和 c 的(空)子节点分别返回 (0, 5) .
a、b 和 c 均返回 (1, 5)。
e 的左(空) child 返回 (0, 5)
d 返回 (2, None)。
e 返回 (2, 5)。
f 返回 (4, None)。