Основи програмирања: вежбе - XIV недеља
Задатак 1
За дат корен бинарног стабла написати функцију која враћа максималну дубину чвора која се може уочити у датом стаблу.
Решење
# Дефиниција чвора бинарног стабла.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
def maxDepth(root):
if not root:
return 0
return 1 + max(maxDepth(root.left),maxDepth(root.right))
# Тест стабло:
"""
root = TreeNode(17)
root.left = TreeNode(7)
root.right = TreeNode(23)
root.left.left = TreeNode(4)
root.left.right = TreeNode(12)
root.right.left = TreeNode(19)
root.left.left.left = TreeNode(1)
print(maxDepth(root))
"""
Задатак 2
За дат корен бинарног стабла написати функцију која враћа дужину његовог диjаметра.
Диjаметар бинарног стабла jе дужина наjдуже путање између два чвора у стаблу и представљена је броjем ивица измећу њих.
Решење
# Дефиниција чвора бинарног стабла.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
def diameterOfBinaryTree(root):
res = [0]
def f(root):
if not root:
return -1
left_height=f(root.left)
right_height=f(root.right)
res[0] = max(res[0],2+left_height+right_height)
return 1 + max(left_height,right_height)
f(root)
return res[0]
# Тест стабло:
"""
root = TreeNode(17)
root.left = TreeNode(7)
root.right = TreeNode(23)
root.left.left = TreeNode(4)
root.left.right = TreeNode(12)
root.right.left = TreeNode(19)
root.left.left.left = TreeNode(1)
print(diameterOfBinaryTree(root))
"""
Задатак 3
За дат корен бинарног стабла написати функциjу коjа ће изокренути стабло и вратити његов корен.
Решење
# Дефиниција чвора бинарног стабла.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
def invertTree(root):
# base case
if not root:
return None
#zamenimo levo dete i desno dete
root.left, root.right = root.right, root.left
#pozovemo rekurziju za levo dete i desno dete
invertTree(root.left)
invertTree(root.right)
return root
# Тест стабло:
"""
root = TreeNode(17)
root.left = TreeNode(7)
root.right = TreeNode(23)
root.left.left = TreeNode(4)
root.left.right = TreeNode(12)
root.right.left = TreeNode(19)
root.left.left.left = TreeNode(1)
new_root = invertTree(root)
print(new_root.val)
print(new_root.left.val)
print(new_root.right.val)
print(new_root.left.right.val)
print(new_root.right.left.val)
print(new_root.right.right.val)
"""
Задатак 4
За дате корене p и q бинарних стабала написати функциjу коjа одређуjе да ли су стабла идентична или не.
Два бинарна стабла се сматраjу идентичним ако су структурално идентична и ако њихови чворови имаjу исте вредности.
Решење
# Дефиниција чвора бинарног стабла.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
def isSameTree(p, q):
#kada oba korena ne postoje
if not p and not q:
return True
#kada jedan ne postoji
if (not p and q) or (not q and p):
return False
#oba postoje ali
#su im vrednosti razlicite
if p.val != q.val:
return False
#oba postoje ali
#su im vrednosti iste
return isSameTree(p.left,q.left) and isSameTree(p.right,q.right)
# Тест стабла:
"""
root = TreeNode(17)
root.left = TreeNode(7)
root.right = TreeNode(23)
root.left.left = TreeNode(4)
root.left.right = TreeNode(12)
root.right.left = TreeNode(19)
root.left.left.left = TreeNode(1)
another_root = TreeNode(17)
another_root.left = TreeNode(7)
another_root.right = TreeNode(23)
another_root.left.left = TreeNode(4)
another_root.left.right = TreeNode(12)
another_root.right.left = TreeNode(19)
#another_root.left.left.left = TreeNode(1)
print(isSameTree(root, another_root))
"""
Задатак 5
За дате корене root и subRoot бинарних стабала, вратити True ако је subRoot корен подстабла у стаблу чији је корен root; у супротном вратити False.
Решење
# Дефиниција чвора бинарног стабла.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
def isSubtree(root, subRoot):
def isSametree(p,q):
if (not p and q) or (not q and p):
return False
if not p and not q:
return True
if p.val != q.val:
return False
return isSametree(p.left,q.left) and isSametree(p.right,q.right)
if not subRoot:
return True
if not root:
return False
if isSametree(root,subRoot):
return True
return isSubtree(root.left,subRoot) or isSubtree(root.right,subRoot)
# Тест стабла:
"""
root = TreeNode(17)
root.left = TreeNode(7)
root.right = TreeNode(23)
root.left.left = TreeNode(4)
root.left.right = TreeNode(12)
root.right.left = TreeNode(19)
root.left.left.left = TreeNode(1)
another_root = TreeNode(7)
another_root.left = TreeNode(4)
another_root.right = TreeNode(12)
#another_root.left.left = TreeNode(1)
print(isSubtree(root, another_root))
"""