题目

题目来源：力扣（LeetCode）

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

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


示例 1：
image.png
输入：[1,1,1,1,1,null,1]
输出：true

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

思路分析

方法一：深度优先搜索

对二叉树进行一次深度优先搜索，在这过程中，将节点值加入 Set 集合中，在遍历完后二叉树后，判断 Set 集合的大小。

JS 中的 Set 集合中的元素的值都是唯一的，没有重复的值，因此，如果Set 集合中的元素个数大于1，说明二叉树每个节点上的值都不是相同，这棵二叉树不是单值二叉树。

  1. /**
  2.  * Definition for a binary tree node.
  3.  * function TreeNode(val, left, right) {
  4.  *     this.val = (val===undefined ? 0 : val)
  5.  *     this.left = (left===undefined ? null : left)
  6.  *     this.right = (right===undefined ? null : right)
  7.  * }
  8.  */
  9. /**
  10.  * @param {TreeNode} root
  11.  * @return {boolean}
  12.  */
  13. var isUnivalTree = function(root) {
  14.   const set = new Set()
  15.   dfs(root)
  16.   // 如果set集合的大小大于 1，说明不是一棵单值二叉树
  17.   return set.size > 1 ? false : true
  19.   // 遍历二叉树，将树中的节点加入 set 集合中
  20.   function dfs(root){
  21.     if (root != null) {
  22.       set.add(root.val)
  23.       dfs(root.left)
  24.       dfs(root.right)
  25.     }
  26.   } 
  28. };

方法二：递归

如果一颗树是单值的，那么根节点的子节点所在的子树也是单值的，同时根节点的值与子节点的值相同。

  1. 我们把根节点的值当做一个基准，如果和根节点的值不同，那么就不是单值二叉树，否则是单值二叉树。
  2. 遍历一次二叉树，每次和根节点的值比较即可。
  3. 创建一个递归函数，判断每个数的节点是否与给定值相等。
  1. /**
  2.  * Definition for a binary tree node.
  3.  * function TreeNode(val, left, right) {
  4.  *     this.val = (val===undefined ? 0 : val)
  5.  *     this.left = (left===undefined ? null : left)
  6.  *     this.right = (right===undefined ? null : right)
  7.  * }
  8.  */
  9. /**
  10.  * @param {TreeNode} root
  11.  * @return {boolean}
  12.  */
  13. const isUnivalTree = root => {
  14.   // 定义一个递归函数，判断当前节点是否和给定值相等
  15.   const check = (node, val) => {
  16.     // 递归出口：节点空，返回true
  17.     if (!node) return true;
  18.     // 当前节点值与根节点值不相等，返回false
  19.     if (node.val !== val) return false;
  20.     // 返回上一级的内容：左子树和右子树是否都相等
  21.     return check(node.left, val) && check(node.right, val);
  22.   };
  23.   // 将根节点放入函数，根节点的值作为给定值
  24.   return check(root, root.val);
  25. };