• 力扣105. 从前序与中序遍历序列构造二叉树


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

    题目描述

    在这里插入图片描述在这里插入图片描述

    思路

    首先明确:

    1.前序遍历的顺序是根-左-右(即先遍历根节点,再左子树,再右子树)
    2.中序遍历的顺序是左-右-根

    1.前序遍历数组中的第一个元素一定是树的根节点
    2.每次在前序数组中找出根节点,再到的中序数组中找出根节点,则在中序数组中该根节点的左侧为根节点的左子树、右侧是根节点的右子树(则我们每次要重复该操作去构造二叉树

    解题方法

    1.定义构造二叉树的递归函数TreeNode* build(vector& preorder, int preStart, int preEnd, vector& inorder, int inStart, int inEnd)其中preStart是每次递归前序遍历数组中的起始位置preEnd是每次递归前序遍历数组中的结束位置,同理inStart 每次递归中序遍历数组的起始位置inEnd每次递归数组的结束位置
    2.定义一个unordered_mapvalToIndex;在中序遍历数组中每次根节点的索引位置
    3.每次递归中先在先序数组中取出
    当前的父节点
    再再中序数组中找出当前父节点的索引(index),通过计算得到左子树所有节点的长度:int leftSize = index - inStart;
    4.下一次递归的起始与结束位置为preStart + 1, preStart + leftSize,inStart, index - 1,preStart + leftSize + 1,index + 1, inEnd

    复杂度

    时间复杂度:

    O ( n ) O(n) O(n);其中 n n n为树节点的个数

    空间复杂度:

    O ( h e i g h ) O(heigh) O(heigh);其中 h e i g h t height height为树的高度

    Code

    /**
     * Definition for a binary tree node.
     * struct TreeNode {
     *     int val;
     *     TreeNode *left;
     *     TreeNode *right;
     *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
     *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
     *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
     * };
     */
    class Solution {
        //Recode the element of inorder array into the unorderd_map
        unordered_map<int, int>valToIndex;
    public:
        TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
            for (int i = 0; i < inorder.size(); ++i) {
                valToIndex[inorder[i]] = i;
            }
    
            return build(preorder, 0, preorder.size() - 1, inorder, 0, inorder.size() - 1);
        }
    
        TreeNode* build(vector<int>& preorder, int preStart, int preEnd, vector<int>& inorder, int inStart, int inEnd) {
            //Base case
            if (preStart > preEnd) {
                return nullptr;
            }
            //The first element in preorder array is the root of binary tree that
            //we shoud creat
            int rootVal = preorder[preStart];
            //Find the index of rootVal in inorder array
            int index = valToIndex[rootVal];
            //Calculate the size of left tree
            int leftSize = index - inStart;
    
            //Create the root firstly
            TreeNode* root = new TreeNode(rootVal);
            // Recursively construct the left and right subtrees
            root -> left = build(preorder, preStart + 1, preStart + leftSize, inorder, inStart, index - 1);
            root -> right = build(preorder, preStart + leftSize + 1, preEnd, inorder, index + 1, inEnd);
            return root;
        }
    };
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
  • 相关阅读:
    Python爬虫|Scrapy 基础用法
    第14章Linux实操篇-RPM与YUM
    AVL树大总结
    MySQL 索引
    使用Java操作Redis
    kickstarter众筹运营分享
    Luffy项目:2、项目需求(2),项目库的创建,软件开发目录,Django配置文件介绍
    使用 Elasticsearch 作为向量数据库:深入研究 dense_vector 和 script_score
    【开发篇】八、SpringBoot整合MongoBD
    rust组织结构
  • 原文地址:https://blog.csdn.net/LNsupermali/article/details/136611967