Ruby Golf .....

  • 0

    Golf version:

    def count_unival_subtrees(r)

    More readable version:

    def count_unival_subtrees(root)
      count = 0
      unival = -> root {
        count += 1 if [root.left, root.right]
                      .map { |kid| !kid || unival[kid] && kid.val == root.val }
      unival[root] if root

  • 1

    @StefanPochmann what about Python?

    def countUnivalSubtrees(self, root):
        def f(root):
            if not root: return 0, set()
            nbl, dl, nbr, dr = f(root.left) + f(root.right)
            d = dl | dr | {root.val}
            return nbl + nbr + (len(d) == 1), d
        return f(root)[0]

  • 1

    @agave Ok, here's another one:

    def countUnivalSubtrees(self, root):
        def f(r, v):
            if not r: return 0
            x = f(r.left, r.val) + f(r.right, r.val)
            return x + (x.imag < 1) + (r.val != v) * 1j
        return int(f(root, 0).real)

  • 0

    @StefanPochmann nice job but the code is not intelligible :D

  • 1

    @agave Meh, totally easy. The real part is the number of unival subtrees, and the imaginary part is the number of violations (where a child doesn't match the parent's value). So just add those from the two subtrees, and increment them as appropriate (increment the number of unival subtrees if there's no violation, and increment the number of violations if this node doesn't match its parent).

Log in to reply

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.