P-8-1. 樹上的推銷員

def dfs(v,p,tour): # visit v, parent p
    tour.append(v) # first arrive v
    for u in adj[v]:
        if u == p: continue
        dfs(u,v,tour) # visit u
        tour.append(v) # back to v
    return
#
n = int(input())
adj = [[] for i in range(n)]
total = 0
for i in range(n-1):
    u,v,w = [int(x) for x in input().split()]
    total += w
    adj[u].append(v)
    adj[v].append(u)
# sort adj
for i in range(n):
    adj[i].sort()
tour = []
dfs(0,-1,tour)
print(total*2)
print(*tour)

P-8-2. 物流派送系統

#這是我自己寫的 算是暴力解 沒有繼承前一個點的狀態
n = int(input())
adj = [[] for i in range(n)]
c = [0 for i in range(n)]
for i in range(1,n):
    a,b = map(int,input().split())
    adj[i].append(a)
    c[i] = b

def dfs(s):
    ans = 0
    for i in adj[s]:
        c[s] += c[i]
        ans = max(ans,1 +dfs(i))
    return ans
ma = -1
for i in range(n):
    ma = max(dfs(i),ma)
print(max(c))
print(ma)

#解答有優化 繼承前一個點的狀態
def dfs(v):
    global d,step
    for u in child[v]:
        d[u] = d[v] + leng[u]
        step[u] = step[v] + 1
        dfs(u)
n = int(input())
child = [[] for i in range(n)]
leng = [0]*n
for i in range(1,n):
    v,w = [int(x) for x in input().split()]
    child[v].append(i)
    leng[i] = w # length of edge (parent[i],i)
d = [0]*n
step = [0]*n
dfs(0)
print(max(d))
print(max(step))

112選手題R樹的直徑

def dfs(v, parent):
    max_depth = 0
    for i in adj[v]:
        if i != parent:
            max_depth = max(max_depth, dfs(i, v) + 1)
    return max_depth
n = int(input())
adj = [[] for _ in range(n + 1)]
for i in range(n - 1):
    a, b = map(int, input().split())
    adj[a].append(b)
    adj[b].append(a)
ma = 0
fnode = 0
for i in range(1, n + 1):
    distance = dfs(i, -1)
    if distance > ma:
        ma = distance
        fnode = i
print(ma)

樹的遍歷

class TreeNode:
    def __init__(self, val: int):
        self.val: int = val
        self.left = None
        self.right= None 
n1 = TreeNode(val=1)
n2 = TreeNode(val=2)
n3 = TreeNode(val=3)
n4 = TreeNode(val=4)
n5 = TreeNode(val=5)
n6 = TreeNode(val=6)
n7 = TreeNode(val=7)
n1.left = n2
n1.right = n3
n2.left = n4
n2.right = n5
n3.left = n6
n3.right = n7
def forward(node: TreeNode):#前序遍歷
    if node is None:
        return []
    return [node.val] + forward(node.left) + forward(node.right)
print(forward(n1))
#[1, 2, 4, 5, 3, 6, 7]
def mid(node: TreeNode):#中序遍歷
    if node is None:
        return []
    return mid(node.left) + [node.val] + mid(node.right)
print(mid(n1))
#[4, 2, 5, 1, 6, 3, 7]
def back(node: TreeNode):#後序遍歷
    if node is None:
        return []
    return back(node.left) + back(node.right) + [node.val]
print(back(n1))
#[4, 5, 2, 6, 7, 3, 1]

二元樹資訊

n = int(input())
adj = [[] for i in range(n)]
adj2 = [[] for i in range(n)]
for i in range(n):
    p, l, r = map(int, input().split())
    adj[p].append(l)
    adj[p].append(r)
    if l != -1:
        adj2[l].append(p)
    if r != -1:
        adj2[r].append(p)
def parent(n):
    for i in range(len(adj)):
        if len(adj[i]) >= 2:
            if adj[i][0] == n or adj[i][1] == n:
                return i
    return -1
def degree(n):
    ans = 0
    for i in adj[n]:
        if i != -1:
            ans += 1
    return ans
def depth(n, ans):
    if not adj2[n]:
        return ans
    return depth(adj2[n][0], ans + 1)
def height(n):
    if n == -1:
        return 0
    if adj[n][0] != -1:
        lh = height(adj[n][0])
    else:
        lh = 0
    if adj[n][1] != -1:
        rh = height(adj[n][1])
    else:
        rh = 0
    return max(lh, rh) + 1
for i in range(n):
    print(f"node {i}: parent = {parent(i)}, degree = {degree(i)}, depth = {depth(i, 0)}, height = {height(i)-1},")

P-8-4. 樹的高度與根 (同P-3-1) (APCS201710)

n = int(input())
adj = [[] for _ in range(n+1)]
bol = [1] + [0 for i in range(n)]
for i in range(n):
    z = [int(x) for x in input().split()]
    for j in range(1, len(z)):
        adj[i+1].append(z[j])
        bol[z[j]] = 1
def dfs(v):
    ma = 0
    for i in adj[v]:
        ma = max(ma,dfs(i)+1)
    return ma
print(bol.index(0))
ans = 0
for i in range(n):
    ans += dfs(i)
print(ans)

技藝商科111PP-二元樹

def build(preorder, inorder):
    if not preorder or not inorder:
        return []
    root = preorder[0]
    root_index = inorder.index(root)
    left = inorder[:root_index]#中序的左子樹
    right = inorder[root_index + 1:]#中序的右子樹
    lp = preorder[1 :1 + len(left)]#前序的左子樹
    rp = preorder[1 + len(left):]#前序的右子樹
    left_postorder = build(lp, left)
    right_postorder = build(rp, right)
    return left_postorder + right_postorder + [root]
try:
    while True:
        preorder,inorder = map(str,input().split())
        postorder = build(preorder, inorder)
        print(''.join(postorder))
except EOFError:
    pass