leetcode--965--单值二叉树

题目：
如果二叉树每个节点都具有相同的值，那么该二叉树就是单值二叉树。

只有给定的树是单值二叉树时，才返回 true；否则返回 false。

示例 1：

image.png

输入：[1,1,1,1,1,null,1]
输出：true
示例 2：

image.png
输入：[2,2,2,5,2]
输出：false

提示：

给定树的节点数范围是 [1, 100]。
每个节点的值都是整数，范围为 [0, 99] 。

链接：https://leetcode-cn.com/problems/univalued-binary-tree

思路：
1、广度优先遍历一遍二叉树，判断二叉树中元素是否完全一样

Python代码：

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):

    def bfs(self, root):
        if not root:
            return True
        deque = [root]
        val = root.val

        while deque:
            nex = []
            for item in deque:
                if item.val != val:
                    return False
                if item.left:
                    nex.append(item.left)
                if item.right:
                    nex.append(item.right)
            deque = nex
        return True


    def isUnivalTree(self, root):
        """
        :type root: TreeNode
        :rtype: bool
        """
        if not root:
            return True
        return self.bfs(root)

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 bfs(TreeNode* root){
        if (root == nullptr){
            return true;
        }
        vector<TreeNode* > deque;
        deque.push_back(root);

        int val = root->val;
        while(deque.size()>0){
            vector<TreeNode* > nex;
            for (auto item : deque){
                if (item->val != val){
                    return false;
                }
                if (item->left){
                    nex.push_back(item->left);
                }
                if (item->right){
                    nex.push_back(item->right);
                }
            }
            deque.swap(nex);
        }
        return true;
    }

    bool isUnivalTree(TreeNode* root) {
        return bfs(root);
    }
};