Concise and clear C++ easy to understand solution

  • 0

    A tree is universal has two steps:

    1. the left subtree is universal and the right subtree is uni-value.
    2. root value is same as right child(if exists) and left child(if exists)

    DFS method. Using count to store the # of current uni-value. The boolean helper() function returns whether the current tree is uni-value.

    int countUnivalSubtrees(TreeNode* root) {
        if (!root) return 0;
        int cnt=0;
        helper(root, cnt);
        return cnt;
    bool helper(TreeNode* root, int& cnt) {
        if (!root) return true;
        bool isLeft = helper(root->left, cnt);
        bool isRight = helper(root->right, cnt);
        bool tmp1 = root->left? root->val==root->left->val : true;
        bool tmp2 = root->right? root->val==root->right->val : true;
        bool isRoot = isLeft && isRight && tmp1 && tmp2;
        if (isRoot) cnt++;
        return isRoot;

Log in to reply

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