Count Univalue Subtrees

LeetCode Link

Problem Description

Visit LeetCode for the full problem description.

---

Solutions

Solution 1: C# (Best: 108 ms)

Metric	Value
Runtime	108 ms
Memory	N/A
Date	2018-05-03

Solution

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left;
 *     public TreeNode right;
 *     public TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public int CountUnivalSubtrees(TreeNode root) {
      if (root == null) return 0;
    int count = 0;
    CountUnivalSubtreesHelper(root, ref count);
    return count;
}

private bool CountUnivalSubtreesHelper(TreeNode root, ref int count)
{
    if (root == null) return true;
    var leftUniVal = CountUnivalSubtreesHelper(root.left, ref count);
    var rightUniVal = CountUnivalSubtreesHelper(root.right, ref count);
    if (leftUniVal && rightUniVal
    && (root.left == null || root.left.val == root.val)
    && (root.right == null || root.right.val == root.val))
    {
        count++;
        return true;
    }
    return false;
    
}
}

📜 1 more C# submission(s)

Submission (2018-05-03) — 128 ms, N/A

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left;
 *     public TreeNode right;
 *     public TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public int CountUnivalSubtrees(TreeNode root) {
      if(root==null) return 0;

    var result = CountUnivalSubtreesHelper(root, root.val) ? 1 : 0;
    Console.WriteLine($"{root.val} {result}");
    return result + CountUnivalSubtrees(root.left)
    + CountUnivalSubtrees(root.right); ;
    
    
}

private bool CountUnivalSubtreesHelper(TreeNode root, int val)
{   
    if(root==null) return true;
    return root.val==val
          && CountUnivalSubtreesHelper(root.left,val)
          && CountUnivalSubtreesHelper(root.right,val);
}
}

---

Complexity Analysis

Approach	Time	Space
Solution	To be analyzed	To be analyzed