Основи програмирања

БРТСИ1300 / ОЕ1-ОП

View on GitHub

Основи програмирања: вежбе - 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))
"""