Count Univalue Subtrees

• Medium
• keyword: Recursion, single OR
• 类似: Binary Tree Upside-down

Given a binary tree, count the number of uni-value subtrees. A Uni-value subtree means all nodes of the subtree have the same value.

• eg: 如下图中, 有4个univalve subtrees: 每一个leaf都是, 加上右子树: '5-5'

   5       
  / \   
 /   \  
 1   5   
/ \   \ 
4 6   5

树的递归到了边界有2种判断:

• root == null.
• root.left == root.right == null.
• 此二者的区别为何?

idea1

• 由于univale是整个subtrees val的关系, 所以要自底向上的检查, 于是用recursion.
• 边界条件很容易: leaf都是unival subtree.

• 向上走的时候判断左右子树是否为unival, 而且: 若都为unival subtrees, 则判断是否都和root相同, 相同的话, 包括这个root也是一个unival subtree. 判断是否儿子和root相等. 只要有一个儿子和父亲不等, 那么这个父亲就无法和儿子们形成unival.

• 代码如下: 参考: Stephan Pochmann的答案

public int countUnivalSubtrees(TreeNode root) {
    int[] cnt = new int[1];
    all(root, 0, cnt);
    return cnt;
}

// 这里parentVal param有点像cpcs的dfsBottomUp, BST upside down的写法
private boolean rec(TreeNode root, int parentVal, int[] cnt) {
    if (root == null)  return true;
    if (!rec(root.left, root.val, cnt) | !rec(root.right, root.val, cnt) {
        return false;
    }
    cnt[0]++;
    return root.val == parentVal;
}

• 走一遍右子树的部分: 5看左子树为空, 所以直接返回true, 而看右子树的话则要leaf 5走完, 并返回true. 此时的true是因为leaf 5判断parent 5是相等的, 所以为true. 细细品味post-order(即logic after recursion call是walk-up the tree)

idea2

• 也是一个思路, 不过判断父亲和儿子们的时候有点区别
• 代码如下:

private boolean rec(TreeNode root, int[] cnt) {
    if (root == null)  return true;
    if (rec(root.left, cnt) && rec(root.right, cnt)) {
        if (root.left != null && root.left.val != root.val) {
            return false;
        }
        if (root.right != null && root.right.val != root.val) {
            return false;
        }
        cnt[0]++;
        return true;
    }
    return false;
}