【天梯】python L2-006 树的遍历 (25 point(s))

树

L2-006 树的遍历 (25 point(s))

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

n=int(input())
host=list(map(int,input().split()))
inorder=list(map(int,input().split()))


def buildTree(inorder, postorder) -> TreeNode:
    def helper(in_left, in_right):
        
    # 如果这里没有节点构造二叉树了，就结束
        if in_left > in_right:
            return None

        # 选择 post_idx 位置的元素作为当前子树根节点
        val = postorder.pop()
        root = TreeNode(val)

        # 根据 root 所在位置分成左右两棵子树
        index = idx_map[val]

        # 构造右子树
        root.right = helper(index + 1, in_right)
        # 构造左子树
        root.left = helper(in_left, index - 1)
        return root
    idx_map = {val:idx for idx, val in enumerate(inorder)} 
    return helper(0, len(inorder) - 1)

p=buildTree(inorder,host)
q=[p]
res=[]
while(len(q)!=0):
    m=q.pop(0)
    if m!=None:
        res.append(m.val)
    if m.left!=None:
        q.append(m.left)
    if m.right!=None:
        q.append(m.right)
print(*res)

L2-011 玩转二叉树 (25 point(s))

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

n=int(input())
inorder=list(map(int,input().split()))
pre=list(map(int,input().split()))


def buildTree(inorder, preorder) -> TreeNode:
    if not preorder:
        return None
    root = TreeNode(preorder[0])
    stack = [root]
    inorderIndex = 0
    for i in range(1, len(preorder)):
        preorderVal = preorder[i]
        node = stack[-1]
        if node.val != inorder[inorderIndex]:
            node.left = TreeNode(preorderVal)
            stack.append(node.left)
        else:
            while stack and stack[-1].val == inorder[inorderIndex]:
                node = stack.pop()  
                inorderIndex += 1
            node.right = TreeNode(preorderVal)
            stack.append(node.right)

    return root

def change(a):
    if not a:
        return
    else:
        tep=a.left
        a.left=a.right
        a.right=tep
        change(a.left)
        change(a.right)

p=buildTree(inorder,pre)
change(p)
q=[p]
res=[]
while(len(q)!=0):
    m=q.pop(0)
    if m!=None:
        res.append(m.val)
    if m.left!=None:
        q.append(m.left)
    if m.right!=None:
        q.append(m.right)
print(*res)