剣指Offer-006-二叉樹の再構成

リンク
牛客OJ:二叉樹を再建する
9度OJ:http://ac.jobdu.com/problem.php?pid=1385
GitHubコード:006-二叉樹の再建
CSDN題解:剣指Offer–006-二叉樹の再構成
牛客OJ
9度OJ
CSDN問題解
GitHubコード
二叉の木を再建する
1385-二叉木の再構築
剣指Offer–006-二叉樹の再構成
006-二叉樹の再建
題意
テーマの説明
二叉の木の前の順序と中の順序が巡回した結果を入力して、二叉の木を再構築してください.
入力された前の順序と中の順序を巡回した結果には重複した数字が含まれていないと仮定します.
入力
シーケンスを巡回します.{1,2,4,7,3,5,6,8}
シーケンスを巡回中{4,7,2,1,5,3,8,6}
二叉の木を再構成して戻ります.
分析
この問題はやはり比較的簡単で、私達は＊前の順序が遍歴しているのを知っています.
再帰思想1.私達は先に順を追ってシーケンスの最初のルートを巡回して決定して、その後中で順次巡回するシーケンスの中でルートの位置を探し当てて、ルートの左側のはその左のサブツリーで、右はその右のサブツリー2です.ルートと左右のサブツリーを構築します.再帰的に1と2を行います.

#include <iostream>
#include <vector>

using namespace std;

//     
#define __tmain main

#ifdef __tmain

#define debug cout

#else

#define debug 0 && cout

#endif // __tmain


#ifdef __tmain
struct TreeNode
{
    int val;
    TreeNode *left;
    TreeNode *right;

    TreeNode(int x)
    : val(x), left(NULL), right(NULL)
    {
    }

    //
    static void PreOrder(TreeNode *root)
    {
        if(root == NULL)
        {
            return;
        }
        cout <<root->val;
        PreOrder(root->left);
        PreOrder(root->right);
    }

    static void InOrder(TreeNode *root)
    {
        if(root == NULL)
        {
            return;
        }
        InOrder(root->left);
        cout <<root->val;
        InOrder(root->right);
    }

 };
#endif // __tmain

/** * Definition for binary tree * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */
class Solution
{
public:
    struct TreeNode* reConstructBinaryTree(vector<int> pre,vector<int> in)
    {
        //                    
        if(pre.size( ) != in.size( ))
        {
            debug <<"the length of PRE and IN should be smae" <<endl;
            return NULL;
        }

        //      0
        int size = pre.size( );
        if(size == 0)
        {
            debug <<"it's a NULL tree(length = 0)" <<endl;
            return NULL;
        }

        int length = pre.size( );
        debug <<"the length of your tree = " <<length <<endl;
        int value = pre[0];      //               
        TreeNode *root = new TreeNode(value);

        debug <<"the root is" <<root->val <<endl;
        //              
        int rootIndex = 0;
        for(rootIndex = 0; rootIndex < length; rootIndex++)
        {
            if(in[rootIndex] == value)
            {
                debug <<"find the root at " <<rootIndex <<" in IN" <<endl;
                break;
            }
        }
        if(rootIndex >= length)
        {
            debug <<"can't find root (value = " <<value <<") in IN" <<endl;
            return NULL;
        }

        ///          
        ///      ,          ,         
        ///      ,           ,       

        ///            ,      in   
        int leftLength = rootIndex;
        int rightLength = length - 1 - rootIndex;
        debug <<"left length = " <<leftLength <<", rightLength = " <<rightLength <<endl;
        vector<int> preLeft(leftLength), inLeft(leftLength);
        vector<int> preRight(rightLength), inRight(rightLength);
        for(int i = 0; i < length; i++)
        {
            if(i < rootIndex)
            {
                //             ,     (leftLegnth = rootIndex) - 1       ,    i+1
                preLeft[i] = pre[i + 1];
                //      (leftLength = rootIndex) - 1       ,  rootIndex     
                inLeft[i] = in[i];
                debug <<preLeft[i] <<inLeft[i] <<" ";

            }
            else if(i > rootIndex)
            {
                //             ,     (leftLegnth = rootIndex) - 1       ,       
                preRight[i - rootIndex - 1] = pre[i];
                //      (leftLength = rootIndex) - 1       ,  rootIndex     ,       
                inRight[i - rootIndex - 1] = in[i];
                debug <<preRight[i - rootIndex - 1] <<inRight[i - rootIndex - 1] <<" ";

            }
        }
        debug <<endl <<"the left tree" <<endl;
        for(int i = 0; i < leftLength; i++)
        {
            debug <<preLeft[i] <<inLeft[i] <<" ";
        }
        debug <<endl;
        debug <<"the right tree" <<endl;
        for(int i = 0; i < rightLength; i++)
        {
            debug <<preRight[i] <<inRight[i] <<" ";
        }
        debug <<endl;


        root->left = reConstructBinaryTree(preLeft, inLeft);
        root->right = reConstructBinaryTree(preRight, inRight);

        return root;
    }





};

int __tmain( )
{
    int pre[] = { 1, 2, 4, 7, 3, 5, 6, 8 };
    int in[] = { 4, 7, 2, 1, 5, 3, 8, 6 };

    vector<int> preOrder(pre, pre + 8);
    vector<int>  inOrder( in,  in + 8);

    Solution solu;
    TreeNode *root = solu.reConstructBinaryTree(preOrder, inOrder);

    cout <<"PreOrder";
    TreeNode::PreOrder(root);
    cout <<endl;

    cout <<"InOrder ";
    TreeNode::InOrder(root);
    cout <<endl;

    return 0;
}