Question

Formatted question description: https://leetcode.ca/all/250.html

 250	Count Univalue Subtrees

 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.

 For example:
 Given binary tree,

    5
   / \
  1   5
 / \   \
5   5   5

 return 4.
     3 leaf nodes
     1 subtree 5-5 of right

 @tag-tree

Algorithm

Check from bottom to top, using post-order traversal, left and right roots, we still call the function recursively.

For the currently traversed node, if the function is called recursively on the left and right child nodes, and the return is true.

Then it means that the value of the current node and the value of the left and right subtrees are the same, then there is another tree, so the result is incremented by 1.

Code

Java

public class Count_Univalue_Subtrees {
    /**
     * Definition for a binary tree node.
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode(int x) { val = x; }
     * }
     */

    // A subtree of a tree T is a tree S consisting of a node in T and all of its descendants in T.

    public class Solution_optimize {

        int res = 0;

        public int countUnivalSubtrees(TreeNode root) {

            isUnival(root, -1);
            return res;
        }

        boolean isUnival(TreeNode root, int val) {
            if (root == null) {
                return true;
            }

            boolean left = isUnival(root.left, root.val); // return meaning left is, and left-val == root-val
            boolean right = isUnival(root.right, root.val);
            if (!left | !right) {
                return false;
            }

            ++res;

            return root.val == val;

        }
    }

    public class Solution {
        private int result = 0;

        public int countUnivalSubtrees(TreeNode root) {
            if (root == null) {
                return result;
            }

            // check selected sub-root and all its decendants
            if (isUnival(root, root.val)) {
                ++result;
            }

            countUnivalSubtrees(root.left);
            countUnivalSubtrees(root.right);

            return result;
        }

        boolean isUnival(TreeNode root, int val) {

            if (root == null) {
                return true;
            }

            return root.val == val && isUnival(root.left, val) && isUnival(root.right, val);
        }
    }
}

// OJ: https://leetcode.com/problems/count-univalue-subtrees/
// Time: O(N)
// Space: O(H) where H is the height of the tree
class Solution {
private:
    int cnt = 0;
    bool postorder(TreeNode *root) {
        if (!root) return true;
        bool left = postorder(root->left), right = postorder(root->right);
        if (left && right
            && (!root->left || root->val == root->left->val)
            && (!root->right || root->val == root->right->val)) {
            ++cnt;
            return true;
        }
        return false;
    }
public:
    int countUnivalSubtrees(TreeNode* root) {
        postorder(root);
        return cnt;
    }
};

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def countUnivalSubtrees(self, root: Optional[TreeNode]) -> int:
        def dfs(root):
            if root is None:
                return True
            left, right = dfs(root.left), dfs(root.right)
            t = True
            if root.left and root.left.val != root.val:
                t = False
            if root.right and root.right.val != root.val:
                t = False
            nonlocal ans
            if left and t and right:
                ans += 1
            return left and t and right

        ans = 0
        dfs(root)
        return ans

############

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
  def countUnivalSubtrees(self, root):
    """
    :type root: TreeNode
    :rtype: int
    """
    self.count = 0

    def dfs(root, pv): # pv -> parent value
      if not root:
        return True
      left = dfs(root.left, root.val)
      right = dfs(root.right, root.val)
      if left and right:
        self.count += 1
        if root.val == pv:
          return True
      return False

    if root:
      dfs(root, root.val)
    return self.count

250 - Count Univalue Subtrees

Question

Algorithm

Code

All Problems

All Solutions

Welcome to Subscribe On Youtube

Question

Algorithm

Code

All Problems

All Solutions