106-LeetCode는 중차순과 후차순을 반복하여 두 갈래 트리를 구성합니다

기사 목록

제목

법1: 귀속

제목

중순과 후순을 두루 훑어보며 두 갈래 나무를 만든다.한 그루의 나무의 중차 역류와 후차 역류에 따라 두 갈래 나무를 구성한다.
주의: 트리에 중복된 요소가 없다고 가정할 수 있습니다.예를 들어 inorder = [9,3,15,20,7] 후서postorder = [9,15,7,20,3]
다음 두 갈래 트리로 돌아가기: 3/\9 20/\15 7

법1: 귀속

사고방식: 중서 역력: 좌 오른쪽 뒷부분 두루 훑어보기: 좌우

뒷순서 서열에 따라 ----- 루트 노드의 값을 얻는다

중서 시퀀스 + 루트 노드의 가치에 따라 -------중서 시퀀스 중 루트 노드의 하표

중간 시퀀스 + 루트 노드의 아래 표식에 따라 - - - 중간 시퀀스에서 왼쪽 트리의 길이를 얻을 수 있습니다

코드는 다음과 같습니다.

#include 
#include 
#include 
#include 
#include 
#include 

using namespace std;

struct TreeNode
{
    int data;
    TreeNode * left;
    TreeNode * right;
    TreeNode(int value)
    {
        data = value;
        left = NULL;
        right = NULL;
    }
};

map<int , int> index;       //     ---- 
TreeNode * myTreeBuild(vector<int> &  inOrder , vector<int> & backOrder , int in_left , int in_right , int back_left ,  int back_right)
{
    if(back_left > back_right)
    {
        return NULL;
    }

    //  
    int root_value = backOrder[back_right];

    //      
    int in_root = index[root_value];

    //  
    int left_len = in_root - in_left;
 
    //                                                            
    //           in_left                in_root                    in_right
    //                                                                                      
    //           back_left          back_left + left_len           back_right

    TreeNode * root = new TreeNode(root_value);
    root->left = myTreeBuild(inOrder , backOrder , in_left , in_root-1 , back_left , back_left + left_len - 1);
    root->right = myTreeBuild(inOrder , backOrder , in_root + 1 , in_right , back_left + left_len , back_right - 1);

    return root;
}


TreeNode * BuildTree(vector<int> & inOrder , vector<int> & backOrder)
{
    if(inOrder.empty() || backOrder.empty())
    {
        return NULL;
    }

    int size = inOrder.size();

    for(int i = 0; i < size ; i++)
    {
        index[inOrder[i]] = i;
    }

    return myTreeBuild(inOrder , backOrder , 0 , size - 1 , 0 , size - 1);
}

//  
void PrintFromTopToBottom(TreeNode * root)
{
    if(root == NULL)
    {
        return;
    }

    list<TreeNode *> l;
    l.push_back(root);

    while(!l.empty())
    {
        TreeNode * temp = l.front();
        cout << temp->data << " ";
        l.pop_front();

        if(temp->left)
        {
            l.push_back(temp->left);
        }
        if(temp->right)
        {
            l.push_back(temp->right);
        }
    }
    cout << endl;
}


int main()
{
    vector<int> inOrder;
    inOrder.push_back(9);
    inOrder.push_back(4);
    inOrder.push_back(12);
    inOrder.push_back(8);
    inOrder.push_back(1);
    inOrder.push_back(2);
    inOrder.push_back(5);

    vector<int> backOrder;
    backOrder.push_back(9);
    backOrder.push_back(12);
    backOrder.push_back(4);
    backOrder.push_back(1);
    backOrder.push_back(5);
    backOrder.push_back(2);
    backOrder.push_back(8);

    TreeNode * root = BuildTree(inOrder , backOrder);
    PrintFromTopToBottom(root);

    return 0;
}

우리가 구축한 두 갈래 트리를 레이어링하여 내보냅니다.

8 4 2 9 12 1 5