求和树转换算法

解题思路

基本步骤：
- 根据前序和中序遍历重建原始二叉树
- 将原始二叉树转换为求和树
- 输出求和树的中序遍历
关键点：
- 满二叉树的特点：每个非叶子节点都有两个子节点
- 求和树节点值 = 左子树所有节点值之和 + 右子树所有节点值之和
- 叶子节点的求和树值为0

代码实现

cpp
java
python

#include <iostream>
#include <vector>
#include <string>
#include <sstream>
using namespace std;

// 树节点定义
struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

// 构建二叉树
TreeNode* buildTree(vector<int>& preorder, int preStart, int preEnd,
                   vector<int>& inorder, int inStart, int inEnd) {
    if (preStart > preEnd) return NULL;
    
    TreeNode* root = new TreeNode(preorder[preStart]);
    
    // 在中序遍历中找根节点位置
    int rootIndex = inStart;
    for (int i = inStart; i <= inEnd; i++) {
        if (inorder[i] == preorder[preStart]) {
            rootIndex = i;
            break;
        }
    }
    
    int leftSubtreeSize = rootIndex - inStart;
    
    // 递归构建左右子树
    root->left = buildTree(preorder, preStart + 1, preStart + leftSubtreeSize,
                         inorder, inStart, rootIndex - 1);
    root->right = buildTree(preorder, preStart + leftSubtreeSize + 1, preEnd,
                          inorder, rootIndex + 1, inEnd);
    
    return root;
}

// 转换为求和树
int convertToSumTree(TreeNode* root) {
    if (root == NULL) return 0;
    
    int oldValue = root->val;
    
    // 递归计算左右子树的和
    int leftSum = convertToSumTree(root->left);
    int rightSum = convertToSumTree(root->right);
    
    // 更新当前节点的值为左右子树的和
    root->val = leftSum + rightSum;
    
    // 返回包含当前节点的子树所有节点值的和
    return oldValue + leftSum + rightSum;
}

// 中序遍历
void inorderTraversal(TreeNode* root, vector<int>& result) {
    if (root == NULL) return;
    
    inorderTraversal(root->left, result);
    result.push_back(root->val);
    inorderTraversal(root->right, result);
}

int main() {
    string line;
    
    // 读取前序遍历
    getline(cin, line);
    istringstream iss1(line);
    vector<int> preorder;
    int num;
    while (iss1 >> num) {
        preorder.push_back(num);
    }
    
    // 读取中序遍历
    getline(cin, line);
    istringstream iss2(line);
    vector<int> inorder;
    while (iss2 >> num) {
        inorder.push_back(num);
    }
    
    // 构建二叉树
    TreeNode* root = buildTree(preorder, 0, preorder.size() - 1,
                             inorder, 0, inorder.size() - 1);
    
    // 转换为求和树
    convertToSumTree(root);
    
    // 获取求和树的中序遍历
    vector<int> result;
    inorderTraversal(root, result);
    
    // 输出结果
    for (int i = 0; i < result.size(); i++) {
        cout << result[i];
        if (i < result.size() - 1) cout << " ";
    }
    cout << endl;
    
    return 0;
}

import java.util.*;

public class Main {
    static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        
        TreeNode(int val) {
            this.val = val;
        }
    }
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        
        // 读取前序遍历
        String[] preStr = sc.nextLine().split(" ");
        int[] preorder = new int[preStr.length];
        for(int i = 0; i < preStr.length; i++) {
            preorder[i] = Integer.parseInt(preStr[i]);
        }
        
        // 读取中序遍历
        String[] inStr = sc.nextLine().split(" ");
        int[] inorder = new int[inStr.length];
        for(int i = 0; i < inStr.length; i++) {
            inorder[i] = Integer.parseInt(inStr[i]);
        }
        
        // 重建二叉树
        TreeNode root = buildTree(preorder, 0, preorder.length - 1, 
                                inorder, 0, inorder.length - 1);
        
        // 转换为求和树
        convertToSumTree(root);
        
        // 输出求和树的中序遍历
        List<Integer> result = new ArrayList<>();
        inorderTraversal(root, result);
        
        // 打印结果
        for(int i = 0; i < result.size(); i++) {
            System.out.print(result.get(i));
            if(i < result.size() - 1) {
                System.out.print(" ");
            }
        }
    }
    
    // 构建二叉树
    private static TreeNode buildTree(int[] preorder, int preStart, int preEnd,
                                    int[] inorder, int inStart, int inEnd) {
        if(preStart > preEnd) return null;
        
        TreeNode root = new TreeNode(preorder[preStart]);
        
        // 在中序遍历中找到根节点位置
        int rootIndex = 0;
        for(int i = inStart; i <= inEnd; i++) {
            if(inorder[i] == preorder[preStart]) {
                rootIndex = i;
                break;
            }
        }
        
        int leftSubtreeSize = rootIndex - inStart;
        
        // 递归构建左右子树
        root.left = buildTree(preorder, preStart + 1, preStart + leftSubtreeSize,
                            inorder, inStart, rootIndex - 1);
        root.right = buildTree(preorder, preStart + leftSubtreeSize + 1, preEnd,
                             inorder, rootIndex + 1, inEnd);
        
        return root;
    }
    
    // 转换为求和树
    private static int convertToSumTree(TreeNode root) {
        if(root == null) return 0;
        
        // 获取原始值
        int oldValue = root.val;
        
        // 递归计算左右子树的和
        int leftSum = convertToSumTree(root.left);
        int rightSum = convertToSumTree(root.right);
        
        // 更新当前节点的值为左右子树的和
        root.val = leftSum + rightSum;
        
        // 返回包含当前节点的子树所有节点值的和
        return oldValue + leftSum + rightSum;
    }
    
    // 中序遍历
    private static void inorderTraversal(TreeNode root, List<Integer> result) {
        if(root == null) return;
        
        inorderTraversal(root.left, result);
        result.add(root.val);
        inorderTraversal(root.right, result);
    }
}

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

def buildTree(preorder, preStart, preEnd, inorder, inStart, inEnd):
    if preStart > preEnd:
        return None
    
    # 创建根节点
    root = TreeNode(preorder[preStart])
    
    # 在中序遍历中找到根节点位置
    rootIndex = inStart
    for i in range(inStart, inEnd + 1):
        if inorder[i] == preorder[preStart]:
            rootIndex = i
            break
    
    leftSubtreeSize = rootIndex - inStart
    
    # 递归构建左右子树
    root.left = buildTree(preorder, preStart + 1, preStart + leftSubtreeSize,
                         inorder, inStart, rootIndex - 1)
    root.right = buildTree(preorder, preStart + leftSubtreeSize + 1, preEnd,
                          inorder, rootIndex + 1, inEnd)
    
    return root

def convertToSumTree(root):
    if not root:
        return 0
    
    # 保存原始值
    oldValue = root.val
    
    # 递归计算左右子树的和
    leftSum = convertToSumTree(root.left)
    rightSum = convertToSumTree(root.right)
    
    # 更新当前节点的值为左右子树的和
    root.val = leftSum + rightSum
    
    # 返回包含当前节点的子树所有节点值的和
    return oldValue + leftSum + rightSum

def inorderTraversal(root, result):
    if not root:
        return
    
    inorderTraversal(root.left, result)
    result.append(root.val)
    inorderTraversal(root.right, result)

def solve():
    # 读取输入
    preorder = list(map(int, input().split()))
    inorder = list(map(int, input().split()))
    
    # 构建二叉树
    root = buildTree(preorder, 0, len(preorder) - 1,
                    inorder, 0, len(inorder) - 1)
    
    # 转换为求和树
    convertToSumTree(root)
    
    # 获取求和树的中序遍历
    result = []
    inorderTraversal(root, result)
    
    # 输出结果
    print(' '.join(map(str, result)))

if __name__ == "__main__":
    solve()

算法分析

时间复杂度：
- 构建二叉树： $\mathcal{O}(n^2)$
- 转换为求和树： $\mathcal{O}(n)$
- 总体： $\mathcal{O}(n^2)$
空间复杂度：
- 递归调用栈： $\mathcal{O}(h)$ ， $h$ 为树高
- 存储结果： $\mathcal{O}(n)$
- 总体： $\mathcal{O}(n)$

题解 | 将满二叉树转换为求和树

求和树转换算法

解题思路

代码实现

算法分析