LeetCode 965. Univalued Binary Tree

Description

https://leetcode.com/problems/univalued-binary-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:

  1. The number of nodes in the given tree will be in the range [1, 100].
  2. Each node’s value will be an integer in the range [0, 99].

Explanation

Traverse each note and see if the value is unique across the tree.

Python Solution

# 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: TreeNode) -> bool:
        if not root:
            return True
        
        self.unique_value = root.val
     
        return self.helper(root)
        
        
    def helper(self, root):        
        if not root:
            return True
                
        if root.val != self.unique_value:
            return False
        
        return self.helper(root.left) and self.helper(root.right)
  • Time Complexity: O(N))
  • Space Complexity: O(1)

Leave a Reply

Your email address will not be published.