Bài 3, Thi tin học trẻ Long An năm 2025

 Đề:

Bài giải:

Giải thuật, xây dựng cây tam phân từ các nút lá (chứa giá trị của mảng dữ liệu nhập) lên nút gốc. 
Code Python

from typing import List, Optional
class Node:
    def __init__(self, index=None, value=None, one=None, second=None,third=None):
        self.one = one
        self.second = second
        self.third = third
        if value == None:
            if third == None:
                self.value = one.value + second.value
                if second.value >= one.value:
                    self.index = second.index
                else:
                    self.index = one.index
            else:
                if second.value >= one.value:
                    topNode = second
                    runNode = one
                else:
                    topNode = one
                    runNode = second
                if third.value >= topNode.value:
                    runNode = topNode
                    topNode = third
                else:
                    if third.value >= runNode.value:
                       runNode = third
                self.index = topNode.index
                self.value = topNode.value + runNode.value 
        else:
            self.value = value
            self.index = index

def build_tree_from_array(arr: List[int]) -> Optional[Node]:
    nodes = [Node(index=index+1,value=val) for index,val in enumerate(arr)]

    while len(nodes) > 1:
        new_nodes = []
        i = 0
        numberOfNode = len(nodes)
        while i < numberOfNode:
            one = nodes[i]
            second = nodes[i + 1]
            if (numberOfNode % 2 == 1) and (i == numberOfNode - 3):
                third = nodes[i + 2]
                i += 3
            else:
                third = None
                i += 2
            parent = Node(index=None,value=None, one=one, second=second, third=third)
            new_nodes.append(parent)
            
        nodes = new_nodes
        numberOfNode = len(nodes)
    
    return nodes[0] if nodes else None

if __name__ == "__main__":
    arr = [12,12, 13, 12, 15,11,12,14,12,13,13]
    root = build_tree_from_array(arr)
    print(root.index)
    print(root.value)
   

Phần nhập, xuất dữ liệu mình chưa làm nha.

Bài viết liên quan