Question

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

Given the root of a binary tree, return the number of uni-value subtrees.

A uni-value subtree means all nodes of the subtree have the same value.

Example 1:

Input: root = [5,1,5,5,5,null,5]
Output: 4

Example 2:

Input: root = []
Output: 0

Example 3:

Input: root = [5,5,5,5,5,null,5]
Output: 6

Constraints:

The number of the node in the tree will be in the range [0, 1000].
-1000 <= Node.val <= 1000

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

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);
        }
    }
}

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

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    private int ans;

    public int countUnivalSubtrees(TreeNode root) {
        ans = 0;
        dfs(root);
        return ans;
    }

    private boolean dfs(TreeNode root) {
        if (root == null) {
            return true;
        }
        boolean left = dfs(root.left);
        boolean right = dfs(root.right);
        boolean t = true;
        if (root.left != null && root.left.val != root.val) {
            t = false;
        }
        if (root.right != null && root.right.val != root.val) {
            t = false;
        }
        if (left && t && right) {
            ++ans;
        }
        return left && t && right;
    }
}

// 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: TreeNode) -> int:
        count = 0

        def is_unival(node):
            nonlocal count
            if not node:
                return True
            
            left_unival = is_unival(node.left)
            right_unival = is_unival(node.right)
            
            if left_unival and right_unival:
                if node.left and node.val != node.left.val:
                    return False
                if node.right and node.val != node.right.val:
                    return False
                count += 1
                return True
            
            return False

        is_unival(root)
        return count


class Solution: # return 2 values
    def countUnivalSubtrees(self, root: TreeNode) -> int:
        def is_unival(node):
            if not node:
                return True, 0
            
            left_unival, left_count = is_unival(node.left)
            right_unival, right_count = is_unival(node.right)
            
            if left_unival and right_unival:
                if node.left and node.val != node.left.val:
                    return False, 0
                if node.right and node.val != node.right.val:
                    return False, 0
                return True, left_count + right_count + 1
            
            return False, 0

        _, count = is_unival(root)
        return count

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func countUnivalSubtrees(root *TreeNode) int {
	ans := 0
	var dfs func(root *TreeNode) bool
	dfs = func(root *TreeNode) bool {
		if root == nil {
			return true
		}
		left, right := dfs(root.Left), dfs(root.Right)
		t := true
		if root.Left != nil && root.Left.Val != root.Val {
			t = false
		}
		if root.Right != nil && root.Right.Val != root.Val {
			t = false
		}
		if left && t && right {
			ans++
		}
		return left && t && right
	}
	dfs(root)
	return ans
}

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number}
 */
var countUnivalSubtrees = function (root) {
    let ans = 0;
    let dfs = function (root) {
        if (!root) {
            return true;
        }
        const left = dfs(root.left),
            right = dfs(root.right);
        let t = true;
        if (root.left && root.left.val != root.val) {
            t = false;
        }
        if (root.right && root.right.val != root.val) {
            t = false;
        }
        if (left && t && right) {
            ++ans;
        }
        return left && t && right;
    };
    dfs(root);
    return ans;
};

/**
 * Definition for a binary tree node.
 * class TreeNode {
 *     val: number
 *     left: TreeNode | null
 *     right: TreeNode | null
 *     constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.left = (left===undefined ? null : left)
 *         this.right = (right===undefined ? null : right)
 *     }
 * }
 */

function countUnivalSubtrees(root: TreeNode | null): number {
    let ans: number = 0;
    const dfs = (root: TreeNode | null): boolean => {
        if (root == null) {
            return true;
        }
        const l: boolean = dfs(root.left);
        const r: boolean = dfs(root.right);
        if (!l || !r) {
            return false;
        }
        if (root.left != null && root.left.val != root.val) {
            return false;
        }
        if (root.right != null && root.right.val != root.val) {
            return false;
        }
        ++ans;
        return true;
    };
    dfs(root);
    return ans;
}

250 - Count Univalue Subtrees

Question

Algorithm

Code

All Problems

All Solutions

Welcome to Subscribe On Youtube

Question

Algorithm

Code

All Problems

All Solutions