题解38|#前序和中序&中序和后序构建二叉树#

1.前序和中序

#include <vector>
class Solution {
public:
    TreeNode* reConstructBinaryTree(vector<int>& preOrder, vector<int>& vinOrder) {
        // write code here
        int p = preOrder.size();
        int v = vinOrder.size();

        if(p == 0 || v == 0) return nullptr;

        TreeNode* root = new TreeNode(preOrder[0]);
        //前序和中序 注意最右边的边界值
        for(int i = 0; i < vinOrder.size(); i++){
            if(preOrder[0] == vinOrder[i]){
                vector<int> leftPre(preOrder.begin() + 1,preOrder.begin() + i + 1);
                vector<int> leftVin(vinOrder.begin(),vinOrder.begin() + i);
                root->left = reConstructBinaryTree(leftPre, leftVin);

                vector<int> rightPre(preOrder.begin() + i + 1,preOrder.end());
                vector<int> rightVin(vinOrder.begin() + i + 1,vinOrder.end());
                root->right = reConstructBinaryTree(rightPre, rightVin);
                break;
            }
        }
        return root;
    }
};

算法思想：

根据前序遍历和中序遍历的特点，可以确定根节点以及左子树和右子树的前序遍历和中序遍历序列。通过递归的方式，不断构建子树，最终构建出整个二叉树。

时间复杂度：

假设二叉树中共有n个节点，每次递归都需要遍历一次中序遍历序列来确定根节点的位置，所以时间复杂度为O(n)。

空间复杂度：

递归过程中需要创建新的vector来存储子树的前序遍历和中序遍历序列，所以空间复杂度为O(n)。

2.中序和后序

#include <vector>
class Solution {
  public:
    TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
        // write code here
        int in = inorder.size();
        int po = postorder.size();

        if (in == 0 || po == 0) return nullptr;

        TreeNode* root = new TreeNode(postorder[po - 1]);
        //中序+后序 注意最左边的边界值；>=0
        for (int i = po - 1, j = 0; i >= 0; i--, j++) {
            if (postorder[po - 1] == inorder[i]) {

                vector<int> leftPost(postorder.begin(), postorder.end() - j - 1);
                vector<int> leftIn(inorder.begin(), inorder.end() - j - 1);
                root->left = buildTree(leftIn, leftPost);

                vector<int> rightPost(postorder.end() - 1 - j, postorder.end() - 1);
                vector<int> rightIn(inorder.end() - j, inorder.end());
                root->right = buildTree(rightIn, rightPost);

                break;
            }
        }
        return root;
    }
};

算法思想：

根据中序遍历和后序遍历的特点，可以确定根节点以及左子树和右子树的中序遍历和后序遍历序列。通过递归的方式，不断构建子树，最终构建出整个二叉树。

时间复杂度：

假设二叉树中共有n个节点，每次递归都需要遍历一次中序遍历序列来确定根节点的位置，所以时间复杂度为O(n)。

空间复杂度：

递归过程中需要创建新的vector来存储子树的中序遍历和后序遍历序列，所以空间复杂度为O(n)。