大家好，我是 @负雪明烛。点击右上方的「+关注」↗，优质题解不间断！

题目大意

判断二叉树中所有的节点的值是否都是相等的。

并且已知，题目给出的二叉树至少有一个节点。

解题方法

二叉树问题大多都可以用「递归」和「迭代」的方法求解。本题也是如此。

左边是 BFS，按照层进行搜索；右边是DFS，先一路走到底，然后再回头搜索。

965. 单值二叉树 - 图1
下面让我们复习一下这两种搜索方式。

BFS

BFS使用队列，把每个还没有搜索到的点依次放入队列，然后再弹出队列的头部元素当做当前遍历点。

BFS总共有两个模板：

模板一：

如果不需要确定当前遍历到了哪一层，只需要访问完所有节点就可以时。

BFS 模板如下：

  1. while queue 不空：
  2.     cur = queue.pop()
  3.     if cur 有效且未被访问过：
  4.         进行处理
  5.     for 节点 in cur 的所有相邻节点：
  6.         if 该节点有效：
  7.             queue.push(该节点)

模板二：

如果要确定当前遍历到了哪一层，需要知道最少移动步数时，BFS 模板如下。

这里增加了 level 表示当前遍历到二叉树中的哪一层了，也可以理解为在一个图中，现在已经走了多少步了。size 表示在当前遍历层有多少个元素，也就是队列中的元素数，我们把这些元素一次性遍历完，即把当前层的所有元素都向外走了一步。

  1. level = 0
  2. while queue 不空：
  3.     size = queue.size()
  4.     while (size --) {
  5.         cur = queue.pop()
  6.         if cur 有效且未被访问过：
  7.             进行处理
  8.         for 节点 in cur的所有相邻节点：
  9.             if 该节点有效：
  10.                 queue.push(该节点)
  11.     }
  12.     level ++;

上面两个是通用模板，在任何题目中都可以用，是要理解并且记住的！

DFS

分享二叉树遍历的模板：先序、中序、后序遍历方式的区别在于把「执行操作」放在两个递归函数的位置。

伪代码在下面。

1. 先序遍历：

  1. def dfs(root):
  2.     if not root:
  3.         return
  4.     执行操作
  5.     dfs(root.left)
  6.     dfs(root.right)

2. 中序遍历：

  1. def dfs(root):
  2.     if not root:
  3.         return
  4.     dfs(root.left)
  5.     执行操作
  6.     dfs(root.right)

3. 后序遍历：

  1. def dfs(root):
  2.     if not root:
  3.         return
  4.     dfs(root.left)
  5.     dfs(root.right)
  6.     执行操作

代码

本题要判断二叉树的所有节点值是否是相同的，并且至少有一个节点。

我们把题目变成：判断所有节点的值是否都等于根节点。

如果使用 BFS，可以使用模板一，因为我们只需要把所有的节点访问一边就行了，不需要知道当前遍历到哪一层。

如果使用 DFS，由于题目没限制我们的访问次序，因此三种遍历方式都是可以的，简单来说可以使用「先序遍历」。

BFS 代码：

  1. # Definition for a binary tree node.
  2. # class TreeNode(object):
  3. #     def __init__(self, x):
  4. #         self.val = x
  5. #         self.left = None
  6. #         self.right = None
  8. class Solution(object):
  9.     def isUnivalTree(self, root):
  10.         """
  11.         :type root: TreeNode
  12.         :rtype: bool
  13.         """
  14.         q = collections.deque()
  15.         q.append(root)
  16.         val = root.val
  17.         while q:
  18.             node = q.popleft()
  19.             if not node:
  20.                 continue
  21.             if val != node.val:
  22.                 return False
  23.             q.append(node.left)
  24.             q.append(node.right)
  25.         return True
  1. /**
  2.  * Definition for a binary tree node.
  3.  * struct TreeNode {
  4.  *     int val;
  5.  *     TreeNode *left;
  6.  *     TreeNode *right;
  7.  *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
  8.  * };
  9.  */
  10. class Solution {
  11. public:
  12.     bool isUnivalTree(TreeNode* root) {
  13.         queue<TreeNode*> q;
  14.         q.push(root);
  15.         int val = root->val;
  16.         while (!q.empty()) {
  17.             TreeNode* node = q.front(); q.pop();
  18.             if (!node) continue;
  19.             if (node->val != val) 
  20.                 return false;
  21.             q.push(node->left);
  22.             q.push(node->right);
  23.         }
  24.         return true;
  25.     }
  26. };

DFS 代码：

  1. # Definition for a binary tree node.
  2. # class TreeNode:
  3. #     def __init__(self, val=0, left=None, right=None):
  4. #         self.val = val
  5. #         self.left = left
  6. #         self.right = right
  7. class Solution:
  8.     def isUnivalTree(self, root: TreeNode) -> bool:
  9.         return self.dfs(root, root.val);
  11.     def dfs(self, root, val):
  12.         if not root: return True
  13.         if root.val != val: return False
  14.         return self.dfs(root.left, val) and self.dfs(root.right, val)
  1. /**
  2.  * Definition for a binary tree node.
  3.  * struct TreeNode {
  4.  *     int val;
  5.  *     TreeNode *left;
  6.  *     TreeNode *right;
  7.  *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
  8.  * };
  9.  */
  10. class Solution {
  11. public:
  12.     bool isUnivalTree(TreeNode* root) {
  13.         return dfs(root, root->val);
  14.     }
  15.     bool dfs(TreeNode* root, int val) {
  16.         if (!root) return true;
  17.         if (root->val != val) return false;
  18.         return dfs(root->left, val) && dfs(root->right, val);
  19.     }
  20. };

复杂度

  • 时间复杂度：965. 单值二叉树 - 图2，965. 单值二叉树 - 图3是二叉树的节点个数。
  • 空间复杂度：965. 单值二叉树 - 图4，无论是 965. 单值二叉树 - 图5还是965. 单值二叉树 - 图6都需要额外的空间。

总结

  1. 遇到二叉树，就 BFS 或者 DFS。

我是 @负雪明烛 ，刷算法题 1000 多道，写了 1000 多篇算法题解，收获阅读量 300 万。
关注我，你将不会错过我的精彩动画题解、面试题分享、组队刷题活动，进入主页 @负雪明烛 右侧有刷题组织，从此刷题不再孤单。