My Concise JAVA Solution


  • 69
    S
    public class Solution {
        public int countUnivalSubtrees(TreeNode root) {
            int[] count = new int[1];
            helper(root, count);
            return count[0];
        }
        
        private boolean helper(TreeNode node, int[] count) {
            if (node == null) {
                return true;
            }
            boolean left = helper(node.left, count);
            boolean right = helper(node.right, count);
            if (left && right) {
                if (node.left != null && node.val != node.left.val) {
                    return false;
                }
                if (node.right != null && node.val != node.right.val) {
                    return false;
                }
                count[0]++;
                return true;
            }
            return false;
        }
    }

  • 0
    This post is deleted!

  • 1
    W

    Cpp version :

    class Solution {
    private:
        int count;
    public:
        int countUnivalSubtrees(TreeNode* root) {
        count=0;
        bool s=isunival(root);
        return count;    
        }
        
        bool isunival(TreeNode* root)
        {
            if(root==NULL)
                return true;
           bool left=isunival(root->left);
           bool right=isunival(root->right);
           if(left&&right)
           {
               if(root->left!=NULL&&root->left->val!=root->val)
               return false;
               if(root->right!=NULL&&root->right->val!=root->val)
               return false;
               count++;
               return true;
           }
           return false;
        }
    };

  • 8
    E

    My I ask why using integer array with single element rather than declaring a instance variable or just a local variable?


  • 11
    Y

    check java pass by reference and pass by value. In this case, if you declare a local variable, the count is going to be keep updated to local values and will not keep the global subtree count.


  • 0
    E

    Oh, I see, thank you! Then pass an Integer wrapper class reference will also work right? or I just declare a instance variable in class field, that can also hold the value.


  • 1
    Y

    You are right! In an interview, an instance variable is usually good enough from my past experience, saves you some time.


  • 0
    W
    This post is deleted!

  • 0
    W

    But isn't array a local variable as well? Why array can work in this case?


  • 1
    Y

    Array is an object and will be passed by reference instead of value.


  • 0
    W

    Thanks! Learned something here


  • 0
    2

    thank you for sharing


  • 0
    A

    Isnt the question same as check if root,right and left have the same value .So if the tree is
    {4,1,5,5,5,#,5} then the unique trees will be
    (5,#,#),(5,#,#),(5,#,5),(5,#,#)


  • 0
    M

    Thanks, learned something about java here


  • 0

    Python version

    class Solution(object):
        def countUnivalSubtrees(self, root):
            Solution.count = 0
            self.helper(root)
            return Solution.count
        
        def helper(self, root):
            if not root:
                return True
            left, right = self.helper(root.left), self.helper(root.right)
            if left and right:
                if root.left and root.val != root.left.val:
                    return False
                if root.right and root.val != root.right.val:
                    return False
                Solution.count += 1
                return True
            return False

  • 4

    思路是先序遍历树的所有的节点,然后对每一个节点调用判断以当前节点为根的子树的所有节点是否相同

        public int countUnivalSubtrees(TreeNode root) {
          if(root == null) return 0;
          int count = isUnivalue(root) ? 1 : 0;
          return count + countUnivalSubtrees(root.left) + countUnivalSubtrees(root.right);
        }
        
        boolean isUnivalue(TreeNode node){
          boolean b = true;
          if(node.left != null){
            b &= node.val == node.left.val;
            b &= isUnivalue(node.left);
          }
          if(node.right != null){
            b &= node.val == node.right.val;
            b &= isUnivalue(node.right);
          }
          return b;
        }

  • 0

    Here you can use the count return value to signal a uni-value tree or not using negative sign. I use negative to indicate the sub trees are NOT uni-value, positive value means the subtrees ARE uni-value. C#

        public int CountUnivalSubtrees(TreeNode root) 
        {
            return Math.Abs(Count(root));
        }
        
        public int Count(TreeNode node)
        {
            if (node == null) return 0;
            
            int left = Count(node.left);
            int right = Count(node.right);
            
            bool isUni = left >= 0 
                            && right >= 0 
                            && (node.left == null || node.left.val == node.val)
                            && (node.right == null || node.right.val == node.val);
            
            int val = Math.Abs(left) + Math.Abs(right) + (isUni ? 1 : 0);
            if (!isUni) val *= -1;
            
            return val;
        }
    

  • 1
    T

    There is no need to use count array.

    public class Solution {
        private int res;
        public int countUnivalSubtrees(TreeNode root) {
            res = 0;
            helper(root);
            return res;
        }
        private boolean helper(TreeNode node){
            if(node == null){
                return true;
            }
            boolean left = helper(node.left);
            boolean right = helper(node.right);
            if(left && right){
                if ((node.left != null && node.val != node.left.val) ||
                    (node.right != null && node.val != node.right.val)){
                        return false;
                }
                res++;
                return true;
            }
            return false;
        }
    }
    

  • 0
    S

    No global variable in Python:

    class Solution(object):
        def countUnivalSubtrees(self, root):
            """
            :type root: TreeNode
            :rtype: int
            """
            def helper(root):
                if root == None:
                    return True, 0  #(if all subtress uni, # uni subtree so far)
                isUni_l, subtree_l = helper(root.left)
                isUni_r, subtree_r = helper(root.right)
                
                if isUni_l and isUni_r:
                    if ((root.left and root.val != root.left.val) or
                        (root.right and root.val != root.right.val)):
                        return False, subtree_l + subtree_r
                    else:
                        return True, subtree_l + subtree_r + 1
                return False, subtree_l + subtree_r          
            return helper(root)[1]
    

  • 0
    F

    Same idea.

    class Solution {
        int count = 0;
        public int countUnivalSubtrees(TreeNode root) {
            if (root == null) {
                return 0;
            }
            traverseSubtree(root);
            return count;
        }
        public boolean traverseSubtree(TreeNode root) {
            if (root.left == null && root.right == null) {
                count++;
                return true;
            }
            boolean left = root.left == null? true : traverseSubtree(root.left);
            boolean right = root.right == null? true : traverseSubtree(root.right);
            int leftValue = root.left == null? root.val: root.left.val;
            int rightValue = root.right == null? root.val: root.right.val;
            if (left && right && leftValue == root.val && rightValue == root.val) {
                count++;
                return true;
            }
            return false;
        }
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.