105 constructing binary trees from preorder and inorder traversal sequences

One 、 Preface

label ： Trees _ Building a binary tree .

Source of problem LeetCode 105 difficulty ： secondary .

Question link ：https://leetcode-cn.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/

 

Two 、 subject

According to a tree's preorder traversal and middle order traversal structure binary tree .

Be careful : You can assume that there are no duplicate elements in the tree .

for example , give

 The former sequence traversal  preorder = [3,9,20,15,7]
 In the sequence traversal  inorder = [9,3,15,20,7]

Return to the following binary tree ：

    3
   / \
  9  20
    /  \
   15   7

 

3、 ... and 、 Ideas

This question has been written before , Review again . Through the first value of the preceding sequence , You can find the current root node and the array of left and right child nodes , The left and right child nodes use the same method to find their child nodes .

Here is 2 A solution , Method 2 is optimized on the basis of method 1 , Find the position of the current root node in the sequence table , Method 2 works hashTable, In time complexity O(1) You can find the position of the root node in the middle order traversal .

 

Four 、 coded

//==========================================================================
/*
* @file    : 105_BuildTree.h
* @label   :  Trees _ Building a binary tree 
* @blogs   : https://blog.csdn.net/nie2314550441/article/details/107580670
* @author  : niebingyu
* @date    : 2020/07/25
* @title   : 105. Construction of binary trees from traversal sequences of preorder and middle order 
* @purpose :  According to a tree's preorder traversal and middle order traversal structure binary tree .
*
*  Be careful :  You can assume that there are no duplicate elements in the tree .
*  for example , give 
*  The former sequence traversal  preorder = [3,9,20,15,7]
*  In the sequence traversal  inorder =  [9,3,15,20,7]
*
*  Return to the following binary tree ：
*     3
*    / \
*   9  20
*     /  \
*    15   7
*
*  source ： Power button （LeetCode）
*  difficulty ： secondary 
*  link ：https://leetcode-cn.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/
*/
//==========================================================================
#pragma once
#include <iostream>
#include <vector>
#include <deque>
#include <algorithm>
#include <assert.h>
using namespace std;

#define NAMESPACE_BUILDTREE namespace NAME_BUILDTREE {
#define NAMESPACE_BUILDTREEEND }
NAMESPACE_BUILDTREE

struct TreeNode 
{
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x, TreeNode* _left = nullptr, TreeNode* _right = nullptr)
        : val(x), left(_left), right(_right) {}
};

class Solution_1 
{  
public:
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) 
    {
        TreeNode* root = nullptr;
        buildTree(&root, preorder, 0, preorder.size() - 1, inorder, 0, inorder.size() - 1);
        return root;
    }

    void buildTree(TreeNode** node, vector<int>& preorder, int preL, int preR, vector<int>& inorder, int inL, int inR)
    {
        //  Parameters are not verified 
        if (preL > preR || inL > inR)
            return ;
        
        assert(preL >= 0 && preL < preorder.size());
        int nodeValue = preorder[preL];
        *node = new TreeNode(nodeValue);
        int index = -1;
        for (int i = inL; i < inorder.size(); ++i)
        {
            if (inorder[i] == nodeValue)
            {
                index = i;
                break;
            }
        }

        assert(index != -1);
        int steps = index - inL;
        buildTree(&((*node)->left), preorder, preL + 1, preL + steps, inorder, inL, inL + steps - 1);
        buildTree(&((*node)->right), preorder, preL + steps + 1, preR, inorder, inL + steps + 1, inR);
    }
};

class Solution_2 
{
private:
    unordered_map<int,int> hash;
public:
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) 
    {
        int n=preorder.size();
        for(int i = 0; i < n; i++) hash[inorder[i]] = i;
        return mybuild(preorder, inorder, 0, n - 1, 0, n - 1);
    }

    TreeNode* mybuild(vector<int>& preorder,vector<int>& inorder, int preL, int preR, int inL, int inR)
    {
        if(preL > preR) return nullptr;
        int index = hash[preorder[preL]];
        TreeNode* root = new TreeNode(preorder[preL]);
        root->left = mybuild(preorder, inorder, preL + 1, index - inL + preL, inL, index - 1);
        root->right = mybuild(preorder, inorder, index - inL + preL + 1, preR, index + 1, inR);
        return root;
    }
};
 Here is the test code //
//  test   Use cases  START
void test(const char* testName, vector<int>& preorder, vector<int>& inorder, TreeNode* expect)
{
    //  The test case , The requested memory has not been released 
    Solution_1 s;
    TreeNode* result = s.buildTree(preorder, inorder);
    assert(result && expect);
    deque<TreeNode*> resDeque;
    deque<TreeNode*> expDeque;
    bool bResult = true;
    resDeque.push_back(result);
    expDeque.push_back(expect);
    while (!resDeque.empty() && !expDeque.empty())
    {
        if (resDeque.front()->val != expDeque.front()->val)
        {
            bResult = false;
            break;
        }
        if (resDeque.front()->left) resDeque.push_back(resDeque.front()->left);
        if (resDeque.front()->right) resDeque.push_back(resDeque.front()->right);
        if (expDeque.front()->left) expDeque.push_back(expDeque.front()->left);
        if (expDeque.front()->right) expDeque.push_back(expDeque.front()->right);
        
        resDeque.pop_front();
        expDeque.pop_front();
    }

    if (!resDeque.empty() || !expDeque.empty())
        bResult = false;

    if (bResult)
        cout << testName << ", solution passed." << endl;
    else
        cout << testName << ", solution failed. " << endl;
}

//  The test case 
void Test1()
{
    TreeNode* tn_15 = new TreeNode(15);
    TreeNode* tn_7 = new TreeNode(7);
    TreeNode* tn_20 = new TreeNode(20, tn_15, tn_7);
    TreeNode* tn_9 = new TreeNode(9);
    TreeNode* tn_3 = new TreeNode(3, tn_9, tn_20);

    vector<int> preorder = { 3,9,20,15,7 };
    vector<int> inorder = { 9,3,15,20,7 };
    TreeNode* expect = tn_3;
    test("Test1()", preorder, inorder, expect);
}

NAMESPACE_BUILDTREEEND
//  test   Use cases  END
//
void BuildTree_Test()
{
    cout << "------ start 105. Construction of binary trees from traversal sequences of preorder and middle order  ------" << endl;
    NAME_BUILDTREE::Test1();
    cout << "------ end 105. Construction of binary trees from traversal sequences of preorder and middle order  --------" << endl;
}

Execution results ：