题目描述

如果一个二叉树中的每个结点拥有相同的值，则这个二叉树是唯一值的。

返回 true 当且仅当给定的树是唯一值的。

样例

输入：[1,1,1,1,1,null,1]
输出：true

输入：[2,2,2,5,2]
输出：false

注意

• 给定的树中结点的个数在 [1, 100] 中。
• 每一个结点的值是一个整数，且在 [0, 99] 中。

算法

(深度优先遍历，DFS / 广度优先遍历，BFS) $O(n)$

1. 取出根结点的值，然后从根结点开始深度（广度）优先遍历。
2. 遍历时，如果当前结点的值都和根结点的值不相等，则返回 false；否则返回两个儿子结点的逻辑与。

时间复杂度

• 每个结点仅遍历一次，故时间复杂度为 $O(n)$。

C++ 代码

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:

    bool check(TreeNode* r, int v) {
        if (r == NULL)
            return true;
        if (r -> val != v)
            return false;

        return check(r -> left, v) && check(r -> right, v);
    }

    bool isUnivalTree(TreeNode* root) {
        int v = root -> val;
        return check(root, v);
    }
};