LeetCode题目笔记——965. 单值二叉树

题目描述

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

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

示例 1：

输入：[1,1,1,1,1,null,1]
输出：true

示例 2：

输入：[2,2,2,5,2]
输出：false

提示：

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

题目链接

题目难度——简单

方法一：遍历+哈希表

  我们可以遍历整个树，用一个集合记录过程中遇到的元素，最后返回这个集合的大小是否为1，即是否所有元素都是同样的值，遍历用前中后任意顺序都可以。只不过这种方法需要遍历完整个树，当然也可以在遍历过程中每次都判断一下集合大小是否为1.

代码/Python

# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def isUnivalTree(self, root) -> bool:
        res = set()
        self.travel(root, res)
        return len(res) == 1
        
    def travel(self, root, table: set):
        if not root:
            return
        
        table.add(root.val)
        # if len(table) > 1:
        	return 
        self.travel(root.left, table)
        self.travel(root.right, table)

方法二：深度优先

  由于这道题至少会有一个根节点，所以我们可以判断根节点的左右子树的值是否都和根节点的值一样，不一样就返回false。

代码/Python

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def isUnivalTree(self, root) -> bool:
        root_val = root.val
        return self.travel(root, root_val)

    def travel(self, root, val):
        if not root:
            return True
        
        if root.val != val:
            return False
        return self.travel(root.left, val) and self.travel(root.right, val)

总结

  两种方法时间复杂度和空间复杂度都为O(N)，使用迭代方法遍历的话，空间复杂度就可以降到O(1)。