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, 100]
.[0, 99]
.Source
# 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
def is_unival_tree(root):
"""Recursive approach (DFS)"""
def dfs(node, x):
# base case
if not node:
return True
if node.val != x:
return False
return dfs(node.left, x) and dfs(node.right, x)
if root:
return dfs(root, root.val)
return True # arbitrary choice
Solve it both recursively and iteratively.
def is_unival_tree(root):
"""Recursive approach (DFS)"""
if not root:
return True # arbitrary choice
x = root.val
stack = [root]
while stack:
node = stack.pop()
if node.val != x:
return False
if node.right:
stack.append(node.right)
if node.left:
stack.append(node.left)
return True
def is_unival_tree(root):
"""alternative version of above solution."""
if not root:
return True # arbitrary choice
x = root.val
stack = [root]
while stack:
node = stack.pop()
if not node:
continue
if node.val != x:
return False
stack += node.left, node.right
return True
def is_unival_tree(root):
"""Recursive approach (BFS)"""
if not root:
return True
x = root.val
queue = [root]
for node in queue: # DIFF HERE
if not node:
continue
if node.val != x:
return False
queue += node.left, node.right
return True