超琐碎 ≈ 完整记录 + 深入探究 + 任性吐槽
问题地址，难度：Easy，标签：Tree
若有错误之处请予以指正:)
问题描述
A binary tree is univalued if every node in the tree has the same value.
Return true if and only if the given tree is univalued.
Example 1:
Input: [1,1,1,1,1,null,1]
Output: true
Example 2:
Input: [2,2,2,5,2]
Output: false
Note:
- The number of nodes in the given tree will be in the range
[1, 100]. - Each node's value will be an integer in the range
[0, 99].
题意分析
这道题需要了解二叉搜索树的定义，以及递归/循环的知识。解决的思路：第一种是递归的每一步只看一对父子的值是否相等，然后传递下去，如果每一对都等，肯定全等；第二种是递归只管把所有节点值取出来，最后看一下是不是全等；第三种是先获取root的值，再递归搜索root的子树看是不是所有节点都等于这个值。
实现方法（及调优过程）
以下前两种方法对应LeetCode上的Solution，第三种是上面没有的。
方法1：60 ms
方法1对应第一种思路，看起来挺容易，但做起来有点绕。
isUnivalTree(root)的结果即是“root所代表的子树是否为全等”这个命题的真值。首先须确定root到底有没有左子树和右子树，如果没有，则真值为True；如果有，则root的值与左右两个子节点的值必须相等，且两个子节点所代表的子树也必须是全等的，两个条件同时满足时真值为True。
下面贴的代码是我参考了Solution以后改的，原来的代码非常简洁（几乎就是逻辑运算式），我只是把逻辑运算的顺序改得清楚了点。
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def isUnivalTree(self, root):
"""
:type root: TreeNode
:rtype: bool
"""
left = (not root.left) or ((root.val == root.left.val) and self.isUnivalTree(root.left))
right = (not root.right) or ((root.val == root.right.val) and self.isUnivalTree(root.right))
return left and right
- 时间复杂度：O(n) （
n为树的节点数，最坏情况下每个节点都被遍历） - 空间复杂度：O(m) （递归本身的栈会占用一些资源，
m为树的深度，影响栈的数量）
方法2：36 ms
方法2对应第二种思路，个人感觉不够优雅，因为遍历完树以后还没有得到最后的答案（真值）。但实现起来容易多了。这里我直接贴了LeetCode上的Solution代码，其组织形式值得理解：values放在isUnivalTree里，isUnivalTree内部再写一个用于递归的函数getValues，这样values的作用域刚好使得getValues少一个丑陋的参数。
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def isUnivalTree(self, root):
"""
:type root: TreeNode
:rtype: bool
"""
values = []
def getValues(node):
if node:
values.append(node.val)
getValues(node.left)
getValues(node.right)
getValues(root)
return len(set(values)) == 1
- 时间复杂度：O(n) （
n为树的节点数，最坏情况下每个节点都被遍历） - 空间复杂度：O(m) （递归本身的栈会占用一些资源，
m为树的深度，影响栈的数量）
方法3：70 ms
方法3的实现从组织方式上参考了方法2，而递归输出了真值则更像方法1，代码里比较tricky的地方是如果当前节点为None时，会返回True（方法1里其实也有这样的逻辑）。
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def isUnivalTree(self, root):
"""
:type root: TreeNode
:rtype: bool
"""
root_val = root.val
def hasUniValue(node):
if node:
return node.val == root_val and hasUniValue(node.left) and hasUniValue(node.right)
else:
return True
return hasUniValue(root)
弄清上面的逻辑后，还可仿照方法1改写hasUniValue，省略if语句。
def hasUniValue(node):
return not node or (node.val == root_val and hasUniValue(node.left) and hasUniValue(node.right))
- 时间复杂度：O(n) （
n为树的节点数，最坏情况下每个节点都被遍历） - 空间复杂度：O(m) （递归本身的栈会占用一些资源，
m为树的深度，影响栈的数量）
