1. ํธ๋ฆฌ๋ฅผ ๋ด์ ๊ตฌ์กฐ ๋ง๋ค๊ธฐ
class node:
def __init__(self, info):
self.number = info[2]
self.data = info[:2]
self.right = None
self.left = None
1-1. ํธ๋ฆฌ์ ๋ ธ๋๋ฅผ ์ถ๊ฐํ๋ ํจ์ ๋ง๋ค๊ธฐ
def addnode(root, info):
if info[0] > root.data[0]:
if not root.right: root.right = node(info)
else: addnode(root.right, info)
elif info[0] < root.data[0]:
if not root.left: root.left = node(info)
else: addnode(root.left, info)
2. ์ ์ ์ํ/ํ์ ์ํ ํจ์ ๋ง๋ค๊ธฐ
def preorder(root, order):
if root != None:
order.append(root.number)
preorder(root.left, order)
preorder(root.right, order)
def preorder(root, order):
if root != None:
postorder(root.left, order)
postorder(root.right, order)
order.append(root.number)
3. ๋ ธ๋๋ฅผ ๊ธฐ์ค์ ๋ง๊ฒ ์ ๋ ฌํ๊ณ ํธ๋ฆฌ๋ฅผ ์์ฑ
def solution(nodeinfo):
nodeinfo = [[*info, idx + 1] for idx, info in enumerate(nodeinfo)]
nodeinfo = sorted(nodeinfo, key=lambda x: x[1], reverse=True)
root = node(nodeinfo[0])
for info in nodeinfo[1:]:
addnode(root, info)
4. ๊ฐ ์ํ์ ๊ฒฐ๊ณผ๋ฅผ ํฉ์น๊ณ ๊ฒฐ๊ณผ๋ฅผ ๋ฐํ
preorderList = []
preorder(root, preorderList)
postorderList = []
postorder(root, postorderList)
return [preorderList, postorderList]
import sys
sys.setrecursionlimit(10**6)
class node:
def __init__(self, info):
self.number = info[2]
self.data = info[:2]
self.right = None
self.left = None
def addnode(root, info):
if info[0] > root.data[0]:
if not root.right: root.right = node(info)
else: addnode(root.right, info)
elif info[0] < root.data[0]:
if not root.left: root.left = node(info)
else: addnode(root.left, info)
def preorder(root, order):
if root != None:
order.append(root.number)
preorder(root.left, order)
preorder(root.right, order)
def postorder(root, order):
if root != None:
postorder(root.left, order)
postorder(root.right, order)
order.append(root.number)
def solution(nodeinfo):
nodeinfo = [[*info, idx + 1] for idx, info in enumerate(nodeinfo)]
nodeinfo = sorted(nodeinfo, key = lambda x: x[1], reverseTrue)
root = node(nodeinfo[0])
for info in nodeinfo[1:]:
addnode(root, info)
preorderList = []
preorder(root, preorderList)
postorderList = []
postorder(root, postorderList)
return [preorderList, postorderList]
1. ํธ๋ฆฌ๋ฅผ ๋ด์ ๊ตฌ์กฐ ๋ง๋ค๊ธฐ
def solution(nodeinfo):
nodeinfo = [[*info, idx + 1] for idx, info in enumerate(nodeinfo)]
y = sorted(nodeinfo, key=lambda x: -x[1])
x = sorted(nodeinfo)
2. ์ ์ ์ํ/ํ์ ์ํ ํจ์ ๋ง๋ค๊ธฐ
def preorder(y, x, answer):
node = y[0]
idx = x.index(node)
left, right = [], []
for i in range(1, len(y)):
if node[0] > y[i][0]: right.append(y[i])
else: left.append(y[i])
answer.append(node[2])
if len(right) > 0: preorder(right, x[:idx], answer)
if len(left) > 0: preorder(left, x[idx + 1], answer)
def postorder(y, x, answer):
node = y[0]
idx = x.index(node)
left, right = [], []
for i in range(1, len(y)):
if node[0] > y[i][0]: right.append(y[i])
else: left.append(y[i])
if len(right) > 0: postorder(right, x[:idx], answer)
if len(left) > 0: postorder(left, x[idx + 1:], answer)
answer.append(node[2])
3. ๊ฐ ์ํ์ ๊ฒฐ๊ณผ๋ฅผ ํฉ์น๊ณ ๊ฒฐ๊ณผ๋ฅผ ๋ฐํ
preorderList = []
postorderList = []
preorder(y, x, preorderList)
postorder(y, x, postorderList)
return [preorderList, postorderList]
def preorder(y, x, answer):
node = y[0]
idx = x.index(node)
left, right = [], []
for i in range(1, len(y)):
if node[0] > y[i][0]: right.append(y[i])
else: left.append(y[i])
answer.append(node[2])
if len(right) > 0: preorder(right, x[:idx], answer)
if len(left) > 0: preorder(left, x[idx + 1], answer)
def postorder(y, x, answer):
node = y[0]
idx = x.index(node)
left, right = [], []
for i in range(1, len(y)):
if node[0] > y[i][0]: right.append(y[i])
else: left.append(y[i])
if len(right) > 0: postorder(right, x[:idx], answer)
if len(left) > 0: postorder(left, x[idx + 1:], answer)
answer.append(node[2])
def solution(nodeinfo):
nodeinfo = [[*info, idx + 1] for idx, info in enumerate(nodeinfo)]
y = sorted(nodeinfo, key=lambda x: -x[1])
x = sorted(nodeinfo)
preorderList = []
postorderList = []
preorder(y, x, preorderList)
postorder(y, x, postorderList)
return [preorderList, postorderList]