/**
 * This problem was asked by Google.
A unival tree (which stands for "universal value") is a tree where all nodes under it have the same value.
Given the root to a binary tree, count the number of unival subtrees.
For example, the following tree has 5 unival subtrees:
    0
   /   1   0
     /     1   0
   /   1   1
 * */

class Node(value_: Int) {
    var value = value_
    var left: Node? = null
    var right: Node? = null
}

class Problem_954 {
    /**
     * solution: check whether if unival tree:
     * 1. leaf node
     * 2. children node has save value
     * */

    fun countUnivalTree(root:Node?):Int{
        return helperCount(root)
    }

    private fun helperCount(node:Node?):Int{
        if (node == null){
            return 0
        }
        if (node.left==null && node.right==null){
            return 1
        }
        var count = 0
        if (node.left?.value == node.right?.value){
            count++
        }
        if (node.left!=null){
            count += helperCount(node.left!!)
        }
        if (node.right!=null){
            count += helperCount(node.right!!)
        }
        return count
    }
}