質問する

プログラマーゲーム

問題を解く

これは再帰関数が適切に実現できるかどうかを測定できる問題のようだ.
問題を解決するプロセスは次のとおりです.

は、

を並べ替えて、所与のノードをツリーに配置する

の問題では、所与の条件を用いて二叉木

を実現する.
前列

、後列

ここで重要なのは,二叉木過程をどのようにうまく実現するかである.
最初は,コードはサブノードから始まり,親ノードに沿って上向きになり,条件に合致することを確認するように実現される.しかし,この方法は,与えられた条件のみを満たしてノード位置を決定する決定的な方法ではなく,条件に合致する親ノードを見つける前に複数のノードを探す必要があるため,O(nlogn)O(nlogn)O(nlogn)O(nlogn)O(nlogn)は効率的ではない.
したがって、親ノードから、条件に従って子ノードを親ノードの下に追加する方法が変更されます.この方法はノードの位置を決定するので,O(logn)O(logn)O(logn)のみがサブノードの位置を決定する.
binary treeが正しく実現されれば,treeを巡るだけで簡単にdfsで実現できる.

# 풀이 1
import sys
sys.setrecursionlimit(10**6)
import heapq

def solution(nodeinfo):
    answer = []
    def make_binary_tree(parent, child):
        if parent[1] > child[1]:
            if tree[parent[2]][0]:
                make_binary_tree(tree[parent[2]][0], child)
            else:
                tree[parent[2]][0] = child
        else:
            if tree[parent[2]][1]:
                make_binary_tree(tree[parent[2]][1], child)
            else:
                tree[parent[2]][1] = child

    def dfs(x):
        preorder.append(x)
        if tree[x] == [0, 0]:
            postorder.append(x)
        else:
            for nxt_node in tree[x]:
                if nxt_node != 0:
                    dfs(nxt_node[2])
            postorder.append(x)
    # 1. init settings
    N = len(nodeinfo)
    max_heap = []
    tree = {}
    
    for i in range(N):
        # [y, x, node_number]
        heapq.heappush(max_heap, [-nodeinfo[i][1], nodeinfo[i][0], i+1])
        tree[i+1] = [0,0]

    root = heapq.heappop(max_heap)

    # 2. set binary tree for preorder, postorder
    while max_heap:
        child = heapq.heappop(max_heap)
        make_binary_tree(root, child)
        
    # 3. traverse by preorder, postorder
    preorder = []
    postorder = []
    dfs(root[2])

    answer.append(preorder)
    answer.append(postorder)
    return answer

# 풀이 2
import heapq

class Node:
    def __init__(self, x, data) -> None:
        self.data = data
        self.x = x
        
class TreeNode:
    def __init__(self, node) -> None:
        self.root = node
        self.left = None
        self.right = None

class BinaryTree:
    def __init__(self) -> None:
        self.head = None
        self.preorder = []
        self.postorder = []

    def push(self, data_node):
        cur = self.head
        node = TreeNode(data_node)
        if cur == None:
            self.head = node
        else:
            while True:
                if node.root.x < cur.root.x:
                    if cur.left:
                        cur = cur.left
                    else:
                        cur.left = node
                        break
                else:
                    if cur.right:
                        cur = cur.right
                    else:
                        cur.right = node
                        break

    def traverse(self, x):
        self.preorder.append(x.root.data)
        if x.left:
            self.traverse(x.left)
        if x.right:
            self.traverse(x.right)
        self.postorder.append(x.root.data)
    

def solution(nodeinfo):
    answer = []
    
    # 1. init settings
    N = len(nodeinfo)
    max_heap = []
    tree = BinaryTree()
    
    for i in range(N):
        # [y, x, node_number]
        heapq.heappush(max_heap, [-nodeinfo[i][1], nodeinfo[i][0], i+1])

    # 2. set binary tree for preorder, postorder
    while max_heap:
        y, x, node = heapq.heappop(max_heap)
        tree.push(Node(x, node))
        
    # 3. traverse by preorder, postorder
    tree.traverse(tree.head)

    answer.append(tree.preorder)
    answer.append(tree.postorder)
    return answer


print(solution([[5,3],[11,5],[13,3],[3,5],[6,1],[1,3],[8,6],[7,2],[2,2]])) # [[7,4,6,9,1,8,5,2,3],[9,6,5,8,1,4,3,2,7]]

bottom-upよりもtreeを実現する方法が良いようです.プール1はclassではなくlist方式でtreeを実現しようとするが,確かにこの方法は可読性が悪く,コードを記述する際も混同されている.次からは安心してclassで体现します