ALDS1_7_D: Reconstruction of a Tree

問題へのリンク

C#のソース

using System;
using System.Collections.Generic;
using System.Linq;

// Q026 木の復元 https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_7_D&lang=jp
class Program
{
    static string InputPattern = "InputX";

    static List<string> GetInputList()
    {
        var WillReturn = new List<string>();

        if (InputPattern == "Input1") {
            WillReturn.Add("5");
            WillReturn.Add("1 2 3 4 5");
            WillReturn.Add("3 2 4 1 5");
            //3 4 2 5 1
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("4");
            WillReturn.Add("1 2 3 4");
            WillReturn.Add("1 2 3 4");
            //4 3 2 1
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    static Dictionary<int, List<int>> mChildNodeListDict = new Dictionary<int, List<int>>();

    struct JyoutaiDef
    {
        internal int CurrNode;
        internal int[] LeftTreeArr;
        internal int[] RightTreeArr;
    }

    static int[] mPreorderArr;
    static int[] mInorderArr;

    static void Main()
    {
        List<string> InputList = GetInputList();

        mPreorderArr = InputList[1].Split(' ').Select(X => int.Parse(X)).ToArray();
        mInorderArr = InputList[2].Split(' ').Select(X => int.Parse(X)).ToArray();

        var Stk = new Stack<JyoutaiDef>();
        JyoutaiDef WillPush;

        int[] LeftTreeArr;
        int CurrNode;
        int[] RightTreeArr;
        DeviceArr(mPreorderArr, out LeftTreeArr, out CurrNode, out RightTreeArr);
        WillPush.CurrNode = CurrNode;
        WillPush.LeftTreeArr = LeftTreeArr;
        WillPush.RightTreeArr = RightTreeArr;
        int RootNode = CurrNode;

        Stk.Push(WillPush);

        while (Stk.Count > 0) {
            JyoutaiDef Popped = Stk.Pop();

            if (mChildNodeListDict.ContainsKey(Popped.CurrNode) == false) {
                mChildNodeListDict[Popped.CurrNode] = new List<int>();
            }

            Action<int[]> PushAct = pArr =>
            {
                DeviceArr(pArr, out LeftTreeArr, out CurrNode, out RightTreeArr);

                mChildNodeListDict[Popped.CurrNode].Add(CurrNode);
                WillPush.CurrNode = CurrNode;
                WillPush.LeftTreeArr = LeftTreeArr;
                WillPush.RightTreeArr = RightTreeArr;
                Stk.Push(WillPush);
            };

            //左部分木のPush
            if (Popped.LeftTreeArr.Length > 0) {
                PushAct(Popped.LeftTreeArr);
            }

            //右部分木のPush
            if (Popped.RightTreeArr.Length > 0) {
                PushAct(Popped.RightTreeArr);
            }
        }
        // 後行順巡回でDFS
        var PostorderNodeList = new List<int>();
        Postorder(RootNode, PostorderNodeList);
        string WillOut = string.Join(" ",
            Array.ConvertAll(PostorderNodeList.ToArray(), pX => pX.ToString()));
        Console.WriteLine(WillOut);
    }

    // 配列を引数として、左部分木、カレントノード、右部分木に分割する
    static void DeviceArr(int[] pTargetArr,
        out int[] pLeftTreeArr, out int pCurrNode, out int[] pRightTreeArr)
    {
        pCurrNode = -1;

        // Preorderで一番最初に訪問したノードがカレントノード
        for (int I = 0; I <= mPreorderArr.GetUpperBound(0); I++) {
            int wkInd = Array.IndexOf(pTargetArr, mPreorderArr[I]);
            if (wkInd >= 0) {
                pCurrNode = mPreorderArr[I];
                break;
            }
        }
        int DeviceInd = Array.IndexOf(mInorderArr, pCurrNode);

        var LeftTreeList = new List<int>();
        var RightTreeList = new List<int>();
        for (int I = 0; I <= mInorderArr.GetUpperBound(0); I++) {
            if (Array.IndexOf(pTargetArr, mInorderArr[I]) == -1)
                continue;

            if (I < DeviceInd) LeftTreeList.Add(mInorderArr[I]);
            if (I > DeviceInd) RightTreeList.Add(mInorderArr[I]);
        }
        pLeftTreeArr = LeftTreeList.ToArray();
        pRightTreeArr = RightTreeList.ToArray();
    }

    // 後行順巡回でDFS
    static void Postorder(int pCurrNode, List<int> pPrintNodeList)
    {
        if (pCurrNode == -1) return;

        mChildNodeListDict[pCurrNode].ForEach(pX => Postorder(pX, pPrintNodeList));
        pPrintNodeList.Add(pCurrNode);
    }
}

解説

PreOrder  行きがけ順 (DFSでの訪問順)
InOrder   通りがけ順
PostOrder 帰りがけ順

ですので、PreOrderとInOrderから、
少しづつ木を特定していってます。