超琐碎 ≈ 完整记录 + 深入探究 + 任性吐槽
问题地址,难度: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
为树的深度,影响栈的数量)
网友评论