二叉樹的遞歸遍歷 - acm1314－IT工程師數位筆記本

文章出處

遺忘 --- 真是一件迷人的事兒。 ---- 某無恥樂觀的小逗比

/**
* 題目： UVa 548 
* 問題描述： 給定一個帶權（權值各不不相同，且都是小于10000的正整數）的二叉樹的中序和后序遍歷， 
* 找一個葉子使得它到樹根路徑上的權值和最小， 如果有多解， 使該葉子結點本身的權值應盡量小。  
* 輸入： 第一行為中序遍歷， 第二行為后續遍歷 
* 示例： 
* 	輸入： 	7 8 11 3 5 16 12 18 
*           8 3 11 7 16 18 12 5 
* 	輸出： 3
* 
* 解決方案： 遞歸建樹 ---- > DFS遍歷方案   
*/

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

//因為各個節點的權值各不相同且都是正整數， 直接用權值作為結點編號  
const int maxv = 10000 + 10; 
int in_order[maxv], post_order[maxv], lch[maxv], rch[maxv]; 
int n; 

bool read_list(int * a)
{
    string line; 
    if(!getline(cin, line)) return false; 
    stringstream ss(line); // 這是一個很有用的類哦。  
    n = 0; 
    int x; 
    while(ss >> x) a[n++] = x; 
    return n > 0; 
}

// 把in_order[L1..R1] 和 post_order[L2..R2]建成一棵二叉樹， 返回樹根 
int build(int L1, int R1, int L2, int R2)
{
    if (L1 > R1) return 0;     // 空樹 
    int root = post_order[R2]; 
    int p = L1; 
    while(in_order[p] != root) p++; 
    int cnt = p - L1;         // 左子樹的結點個數
    lch[root] = build(L1, p-1, L2, L2+cnt-1);
    rch[root] = build(p+1, R1, L2+cnt, R2-1); 
    return root;  
} 

int best, best_sum;     //目前為止的最優解和對應的權和 

void dfs(int u, int sum)
{
    sum += u; 
    if(!lch[u]&&!rch[u]) // 葉子 
    {
        if (sum < best_sum || (sum == best_sum && u < best)) 
        {
            best = u; 
            best_sum = sum; 
        }
    }
    if(lch[u]) dfs(lch[u], sum); 
    if(rch[u]) dfs(rch[u], sum); 
} 

int main()
{
    while(read_list(in_order))
    {
        read_list(post_order); 
        build(0, n-1, 0, n-1); 
        best_sum = 1000000000; // 接近 int 類型的最大值（十位數） 
        dfs(post_order[n-1], 0); 
        cout << best << "\n";  
    }
    return 0; 
}