将满二叉树转换为求和树

[编程题]将满二叉树转换为求和树

热度指数：13742 时间限制：C/C++ 5秒，其他语言10秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

给出满二叉树的前序遍历结果和中序遍历结果，编写算法将其转化为求和树

什么是求和树：二叉树的求和树，是一颗同样结构的二叉树，其树中的每个节点将包含原始树中的左子树和右子树的和。

二叉树：

求和树：

二叉树给出前序和中序输入，求和树要求中序输出；

所有处理数据不会大于int；

数据范围：二叉树的节点数满足 $1 \le n \le 100 \$ ,节点上的值满足 $|val| \le 100 \$

输入描述:

2行整数，第1行表示二叉树的前序遍历，第2行表示二叉树的中序遍历，以空格分割

输出描述:

1行整数，表示求和树的中序遍历，以空格分割

示例1

输入

10 -2 8 -4 6 7 5
8 -2 -4 10 7 6 5

输出

0 4 0 20 0 12 0

算法知识视频讲解

Python

一直鱼

import sys

def p(pre,mid):
    if len(pre) <= 3:
        print(0,sum(pre[1:]),0,end=' ')
        return
    rv = pre.pop(0)
    #因为是满二叉树，所以符合条件的位置一定在[3,len(mid)]里面
    index = mid[3:].index(rv) + 3
    p(pre[:index],mid[:index])
    print(sum(pre),end=' ')
    p(pre[index:],mid[index+1:])
    
pre = list(map(int,input().split(' ')))
mid = list(map(int,input().split(' ')))
p(pre,mid)

编辑于 2020-04-22 19:01:44 回复(0)

Python

康斯坦奇

Python版本。利用输入的中序遍历结果和先序遍历结果获得每个结点的求和。

class TreeNode:
    def __init__(self,val):
        self.val = val
        self.left = None
        self.right = None
class Solution:
    def createTree(self,preOrder,midOrder):
        if len(preOrder) ==0 :
            return None
        root_index = midOrder.index(preOrder[0])
        if len(preOrder) == 1:
            root = TreeNode(0)
        else:
            root = TreeNode(sum(preOrder[1:]))
        left_pre = preOrder[1:root_index+1]
        right_pre = preOrder[root_index+1:]
        left_mid = midOrder[0:root_index]
        right_mid = midOrder[root_index+1:]
        root.left = self.createTree(left_pre,left_mid)
        root.right = self.createTree(right_pre,right_mid)
        return root
    def midTreverse(self,root):
        if root == None:
            return []
        return self.midTreverse(root.left) + [root.val] + self.midTreverse(root.right)
s = Solution()
preOrder = [int(x) for x in input().split()]
midOrder = [int(x) for x in input().split()]
root = s.createTree(preOrder,midOrder)
print(" ".join(list(map(str,s.midTreverse(root)))))

发表于 2019-08-21 18:23:26 回复(0)

Python

zcl_zc

l1 = list(map(int,input().split()))
l2 = list(map(int,input().split()))
n = len(l1)
l3 = [False] * n
l4 = [0] * n
for i in l1:
    index = l2.index(i)
    l,r = index - 1,index + 1
    l3[index] = True
    while l >= 0 and l3[l] == False:
        l4[index] += l2[l]
        l -= 1
    while r < n and l3[r] == False:
        l4[index] += l2[r]
        r += 1
print(' '.join(map(str,l4)))

发表于 2019-08-09 15:47:59 回复(0)

Python

ElonB

"""
本题有如下规律：
求和树的根节点 = 除本身外原二叉树所有子节点之和，
本题中根节点为中序遍历数组中正中间项（满二叉树）
递归求得左右子树，直到子树节点个数为1返回[0]。
需要考虑根节点在两侧的情况，树节点个数为0时，返回空[]
"""
def func(d):
    if len(d) == 1: return [0]
    elif len(d) == 0: return []
    mid = len(d) // 2  # 满二叉树根节点即正中间数值，前序遍历数组本题中用不到，可删除
    return func(d[:mid]) + [sum(d[:]) - d[mid]] + func(d[mid + 1:])


if __name__ == "__main__":
    a = list(map(int, input().strip().split()))
    d = list(map(int, input().strip().split()))
    ans = func(d)
    print(' '.join(map(str, ans)))

未考虑满二叉树这一性质，求解如下：

"""
本题有如下规律：
求和树的根节点 = 除本身外所有子节点之和，
递归求得左右子树，直到子树节点个数为1返回[0]。
需要考虑根节点在两侧的情况，树节点个数为0时，返回空[]

"""
import sys


def func(a, d):
    if len(a) == 1:
        return [0]
    elif len(a) == 0:
        return []
    mid = d.index(a[0])
    d[mid] = sum(d[:]) - d[mid]
    return func(a[1:(mid + 1)], d[:mid]) + \
           [sum(d[:]) - d[mid]] + \
           func(a[(mid + 1):], d[mid + 1:])


if __name__ == "__main__":
    # sys.stdin = open('input.txt', 'r')
    a = list(map(int, input().strip().split()))
    d = list(map(int, input().strip().split()))
    ans = func(a, d)
    print(' '.join(map(str, ans)))

编辑于 2019-07-04 12:34:29 回复(9)