LC: Count Univalue Subtrees - spiralgo/algorithms GitHub Wiki

Count Univalue Subtrees

The Essence:

The recursive definition needs to be noticed: a root constitutes a univalue subtree if and only if its children are also univalue subtrees and its value is equal to those of its children.

We can thus count the number of such subtrees going up the tree. In other words, in a post-order, left-right-root traversal. The global count is incremented each time such a root is found.

In algorithms, computer science and science in general, it's generally important to see what the definitions of concepts imply in order to utilize them for the problem-solving process.

Details:

The problem can be solved in a recursive manner as described above. It can be done both at the parent level by comparing values with the children, or the child level by comparing values with the parent.