Welcome to Subscribe On Youtube

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
    
    

All Problems

All Solutions