105从前序与中序遍历序列构造二叉树

痛定思痛。 2023-03-01 12:34 26阅读 0赞

## 一、前言 ##

标签：树\_构建二叉树。

问题来源LeetCode 105难度：中等。

问题链接：[https://leetcode-cn.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/][https_leetcode-cn.com_problems_construct-binary-tree-from-preorder-and-inorder-traversal]

## 二、题目 ##

根据一棵树的前序遍历与中序遍历构造二叉树。

**注意:** 你可以假设树中没有重复的元素。

例如，给出

前序遍历 preorder = [3,9,20,15,7]
    中序遍历 inorder = [9,3,15,20,7]

返回如下的二叉树：

3
       / \
      9  20
        /  \
       15   7

## 三、思路 ##

这个问题之前有写过，再次复习一下。通过前序第一值，可以找到当前根节点和左右孩子节点数组，左右孩子节点用同样的方法找到它们的孩子节点。

这里提供了2种解决方法，方法二是在方法一的基础上进行了优化，找当前根节点在中序列表中的位置，方法二用了hashTable，在时间复杂度O(1)的情况下就可以找到根节点在中序遍历中的位置。

## 四、编码实现 ##

//==========================================================================
    /*
    * @file    : 105_BuildTree.h
    * @label   : 树_构建二叉树
    * @blogs   : https://blog.csdn.net/nie2314550441/article/details/107580670
    * @author  : niebingyu
    * @date    : 2020/07/25
    * @title   : 105.从前序与中序遍历序列构造二叉树
    * @purpose : 根据一棵树的前序遍历与中序遍历构造二叉树。
    *
    * 注意: 你可以假设树中没有重复的元素。
    * 例如，给出
    * 前序遍历 preorder = [3,9,20,15,7]
    * 中序遍历 inorder =  [9,3,15,20,7]
    *
    * 返回如下的二叉树：
    *     3
    *    / \
    *   9  20
    *     /  \
    *    15   7
    *
    * 来源：力扣（LeetCode）
    * 难度：中等
    * 链接：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)
        {
            // 参数没有校验
            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;
        }
    };
    以下为测试代码//
    // 测试 用例 START
    void test(const char* testName, vector<int>& preorder, vector<int>& inorder, TreeNode* expect)
    {
        // 测试用例，申请的内存没有释放
        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;
    }
    
    // 测试用例
    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
    // 测试 用例 END
    //
    void BuildTree_Test()
    {
        cout << "------ start 105.从前序与中序遍历序列构造二叉树 ------" << endl;
        NAME_BUILDTREE::Test1();
        cout << "------ end 105.从前序与中序遍历序列构造二叉树 --------" << endl;
    }

**执行结果：**

![20200725163209364.png][]

[https_leetcode-cn.com_problems_construct-binary-tree-from-preorder-and-inorder-traversal]: https://leetcode-cn.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/
[20200725163209364.png]: /images/20230208/643c46c50de74db791e5462f9602bc4e.png