3??平衡樹

Time Limit:1000MS? Memory Limit:65535K

題型: 編程題???語言: G++;GCC;VC;JAVA;PYTHON

描述

平衡樹并不是平衡二叉排序樹。
這里的平衡指的是左右子樹的權值和差距盡可能的小。
給出n個結點二叉樹的中序序列w[1],w[2],…,w[n]，請構造平衡樹，并給出平衡樹的先序序列。
平衡樹構造算法如下：
（1）假設平衡樹樹根為序列中元素i，i左側所有元素權值和S1=w[1]+w[2]+...+w[i-1],
其右側所有元素權值和S2=w[i+1]+w[i+2]+...w[n]。在選擇樹根i時要求讓S1-S2的絕對值最小。
例如5個元素序列 {5 4 1 2 3}，選擇4為樹根是最合適的，此時左側權值和5，右側權值和6，差值絕對值最小。
如選擇其他結點為根，左右兩側權值和的差值絕對值會更大。
（2）選定樹根i之后，對序列w[1],w[2],...,w[i-1]和w[i+1],w[i+2],...,w[n]分別構造平衡樹，
作為樹根i的左右子樹。

?5個元素序列 {5 4 1 2 3}的平衡樹如上圖，其先序序列為4 5 2 1 3。

輸入格式

第一行一個整數n；
第二行n個正整數表示二叉樹的中序序列。

輸出格式

n個整數，平衡樹的先序序列。
注意：如果選取樹根時有兩個結點，他們左右兩側權值和的差值絕對值相同，且均為最小值，
我們要求選擇編號更小的結點。例如序列（7,6,2,9），選取6或2做樹根時，兩側權值和的差值絕對值均為4，
此時要求選擇6作為樹根。

輸入樣例

4
7 6 2 9

輸出樣例

6 7 9 2

#include <iostream>
#include <stack>
#include <algorithm>
#include <vector>
#include <set>
#include <string>
using namespace std;
typedef long long ll; // 定義long long類型別名llint n; // 節點數量
vector<ll> w; // 存儲中序序列的權值，索引從1到n
vector<ll> p; // 前綴和數組，p[i]表示w[1]到w[i]的和
vector<int> pre; // 存儲先序遍歷結果的節點索引// 遞歸構建平衡樹的函數
// 參數：
//   l: 當前子樹在中序序列中的左邊界
//   r: 當前子樹在中序序列中的右邊界
void build(int l, int r) {if (l > r) return; // 遞歸終止條件：左邊界超過右邊界ll minDiff = 10000000; // 初始化最小差值為一個大數int rootIndex = l; // 初始化根節點索引為左邊界// 遍歷當前子樹的每個可能作為根節點的位置for (int i = l; i <= r; i++) {// 計算左子樹的權值和：p[i-1] - p[l-1]ll leftSum = p[i - 1] - p[l - 1];// 計算右子樹的權值和：p[r] - p[i]ll rightSum = p[r] - p[i];// 計算左右子樹權值和的差的絕對值ll diff = abs(leftSum - rightSum);// 如果找到更小的差值，更新最小差值和根節點索引if (diff < minDiff) {minDiff = diff;rootIndex = i;}// 注意：題目要求當差值相同時選擇編號較小的節點// 由于i是從左到右遍歷的，所以自動滿足這個條件}// 將當前根節點的索引加入先序序列pre.push_back(rootIndex);// 遞歸構建左子樹build(l, rootIndex - 1);// 遞歸構建右子樹build(rootIndex + 1, r);
}int main() {// 優化輸入輸出ios::sync_with_stdio(false);cin.tie(nullptr);cin >> n; // 讀取節點數量w.resize(n + 1); // 調整w的大小為n+1（索引1到n）p.resize(n + 1, 0); // 調整p的大小為n+1，并初始化為0// 讀取權值并計算前綴和for (int i = 1; i <= n; i++) {cin >> w[i];p[i] = p[i - 1] + w[i]; // p[i] = w[1] + w[2] + ... + w[i]}// 從整個序列構建平衡樹build(1, n);// 輸出先序遍歷結果（輸出的是節點的權值，不是索引）for (int i = 0; i < pre.size(); i++) {cout << w[pre[i]] << ' ';}cout << endl;return 0;
}

?