Skip to content

Instantly share code, notes, and snippets.

@jeb2239
Created November 30, 2020 18:13
Show Gist options
  • Save jeb2239/c5cde4b1fdb3114e6f2ed98d35237bc4 to your computer and use it in GitHub Desktop.
Save jeb2239/c5cde4b1fdb3114e6f2ed98d35237bc4 to your computer and use it in GitHub Desktop.
1361
#buggy code took 20 minutes
class Solution:
def validateBinaryTreeNodes(
self, n: int, leftChild: List[int], rightChild: List[int]
) -> bool:
nparent = [0] * n
for i in range(n):
leftv = nparent[leftChild[i]]
if leftv != -1:
nparent[leftv] += 1
rightv = nparent[rightChild[i]]
if rightv != -1:
nparent[rightv] += 1
count = 0
for v in nparent:
if v>1:
return False
if v == 0:
count += 1
if count!=1:
return False
# find cycles
# return true if find cycle
def dfs(v,visited):
visited[v]=1
for node in (leftChild[v],rightChild[v]):
if node!=-1:
if visited[node]==0:
if dfs(node,visited):
return True
if visited[node]==1:
return True
visited[v]=2
return False
visited=[0]*n
for i in range(n):
if visited[i]==0:
if dfs(i,visited):
return False
return True
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment