华为OD统一考试 - 二叉树计算

题目描述

给出一个二叉树如下图所示：

请由该二叉树生成一个新的二叉树，它满足其树中的每个节点将包含原始树中的左子树和右子树的和。

左子树表示该节点左侧叶子节点为根节点的一颗新树；右子树表示该节点右侧叶子节点为根节点的一颗新树。

输入描述

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

例如：

7 -2 6 6 9

6 7 -2 9 6

输出描述

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

例如：

-2 0 20 0 6

用例

题目解析

本题主要是考察二叉树的中序遍历，前序遍历，以及根据中序遍历和前序遍历还原二叉树结构。

二叉树的中序遍历即：左根右，即先遍历左子树，再遍历根，最后遍历右子树

二叉树的前序遍历即：根左右，即先遍历根，再遍历左子树，最后遍历右子树

二叉树的前序遍历序列中首元素就是根节点，比如题目描述中的前序遍历序列：

6 7 -2 9 6

其中首元素6就是根节点。

知道根节点后，我们就可以去中序遍历序列中找打根值对应的节点，比如题目描述中的中序遍历序列：

7 -2 6 6 9

上面中序遍历序列中有两个值为6的元素，那么他们都有可能为根，我们需要一一判断：

• 如果红色6（第一个6）是根，那么根据中序：“左根右” 的遍历特点，7 -2 就是左子树的中序遍历，6 9 就是右子树的中序遍历
• 如果绿色6（第二个6）是根，那么根据中序：“左根右” 的遍历特点，7 -2 6 就是左子树的中序遍历，9 就是右子树的中序遍历

上面两个情况中，我们根据中序遍历特点，得到了左子树的长度、右子树长度。

而一颗二叉树（子树）的序列长度是固定的，即一颗二叉树（子树）的中序遍历序列和前序遍历序列长度是相同的。

因此，我们通过中序遍历得到左子树、右子树长度，那么就可以在前序遍历中划分出左子树、右子树范围：

比如按照中序遍历序列中红色6（第一个6）作为根的话，那么左子树（7 -2）长度为2，右子树（6 9） 长度2，则前序遍历序列可进行如下划分：

此时，对比前序的左子树和中序的左子树是否节点相同，对比前序的右子树和中序的右子树是否相同

如果左右子树都一致，则当前根是正确根。

如果我们选错根，比如选中序遍历序列中第二个6作为根，则

可以发现中序、前序的左右子树是不一致的。

综上所述，即我们通过前序序列找到二叉树的根节点值（前序序列首元素），然后使用此根值，去中序序列中找根值位置，并划分出左子树长度，右子树长度，然后分别在前序、中序序列中，找出左子树序列、右子树序列，对比是否一致，如果一致，则中序序列中对应根值位置正确，否则错误。

根据前序、中序序列还原二叉树结构，也是按照上面逻辑，具体实现请看代码中buildTree函数，已添加详细注释。

另外，本题需要根据原始树（即根据中序、前序还原出来的树），改造出一个新树，新树的每个节点的值 = 其左右子树的所有节点值之和。

这里，我们可以在定义二叉树节点TreeNode结构时，多定义一个属性childSum用于记录节点的左右子树节点值之和。

这样在构造原始树的递归过程中，就可以完成每个节点的childSum值的计算。

最后输出新树的中序遍历序列即可，具体实现见代码中getMidOrder函数。

import Foundation
func ODTest_2_58() {
    print("输入描述")
    print("2行整数，第1行表示二叉树的中序遍历，第2行表示二叉树的前序遍历，以空格分割")
    let midOrder = (readLine() ?? "").split(separator: " ").map { Int($0) ?? 0 }
    let preOrder = (readLine() ?? "").split(separator: " ").map { Int($0) ?? 0 }
    print("1行整数，表示求和树的中序遍历，以空格分割")

    class TreeNode {
        var num = 0 // 当前节点的值
        var childSum = 0 // 当前节点的左子树+右子树的和
        var leftChild: TreeNode?
        var rightChild: TreeNode?

        init(_ num: Int) {
            self.num = num
            self.childSum = 0
        }
    }

    // 记录中序遍历