文章目录

  1. 从前序与中序遍历序列构造二叉树
  2. 从中序与后序遍历序列构造二叉树
    这两道题都是二叉树的构造，二叉树有三种遍历方式：
    1. 前序：根左右
    2. 中序：左根右
    3. 后序：左右根

  前序+中序得到完整的二叉树，首先由前序确定根结点的值，然后在中序序列中，找到根结点的位置，由此确定左子树的长度，进而可以递归得到完整的二叉树
  同样，中序+后序也可以得到完整的二叉树，首先由后序遍历确定根结点的值，然后找到根结点在中序序列中的位置，确定左子树的长度，进而递归得到完整的二叉树

这里面有两个地方需要注意：

  1. 每次递归的时候，边界的确定。只需要记住一句话：用长度来限制左右边界，当长度为0的时候，退出

例如：
前序=[leftPre, rightPre]
中序=[leftIn,rightIn]
我们找到了根结点下标index，那么左子树长度leftLen=index-leftIn ,那么左子树递归的边界我们可以确定为：
左子树=递归(leftPre+1,leftPre+leftLen,leftIn,leftIn+leftLen-1)
这样，当我们遍历到边界位置的时候，例如，当前的前序和中序都是[1]，那么lenLeft=0，leftPre+1>leftPre+leftLen，leftIn>leftIn+leftLen-1，于是我们就可以利用left>right来退出递归;
同理：确定右子树：
右子树=递归(leftPre+leftLen+1,rightPre,leftIn+leftLen+1,rightIn)

  1. 可利用哈希map提前存储结点值，牺牲空间复杂度，提高查询速度

前序+中序：

/** * 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 {
   
private:
    unordered_map<int,int> mp;
    TreeNode* recur(vector<int>& preorder, int leftPre,int rightPre,vector<int>& inorder,int leftIn,int rightIn){
   
        //边界
        if(leftPre>rightPre) return nullptr;

        //记录左子树的长度
        int leftLen=mp[preorder[leftPre]]-leftIn;

        //执行
        TreeNode* node=new TreeNode(preorder[leftPre]);
        node->left=recur(preorder,leftPre+1,leftPre+leftLen,inorder,leftIn,leftIn+leftLen-1);
        node->right=recur(preorder,leftPre+leftLen+1,rightPre,inorder,leftIn+leftLen+1,rightIn);

        return node;
    }
public:
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
   
        //前序：根左右 中序：左根右；
        //先在中序中找出根结点，然后分出左子树和右子树的长度，然后递归构造二叉树
        int len=preorder.size();
        for(int i=0;i<inorder.size();++i) mp[inorder[i]]=i;
        return recur(preorder,0,len-1,inorder,0,len-1);
    }
};

  中序+后序也是一样的分析：
  我们可以首先根据后序遍历，确定根结点的值，然后找出其在中序中的位置，算出左子树的长度，然后递归
中序=[leftIn,rightIn]
后序=[leftPos,rightPos]
我们找到了根结点下标index，那么左子树长度leftLen=index-leftIn ,那么左子树递归的边界我们可以确定为：
左子树=递归(leftIn,leftIn+leftLen-1,leftPos,leftPos+leftLen-1)
这样，当我们遍历到边界位置的时候，例如，当前的中序和后序都是[1]，那么lenLeft=0，leftIn>leftIn+leftLen-1，leftPos>leftPos+leftLen-1，于是我们就可以利用left>right来退出递归;
同理：确定右子树：
右子树=递归(leftIn+leftLen+1,rightIn,leftPos+leftLen,rightPos-1)

中序+后序

/** * 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 {
   
private:
    unordered_map<int,int> mp;
    TreeNode* dfs(vector<int>& inorder, vector<int>& postorder,int in_left,int in_right,int post_left,int post_right){
   
        //由后序遍历可以得到根节点，然后可以从中序遍历得到左右子树的组成；
        if(in_left>in_right) return nullptr;

        //算出左子树长度
        int len_left=mp[postorder[post_right]]-in_left;

        TreeNode* root=new TreeNode(postorder[post_right]);
        root->left=dfs(inorder,postorder,in_left,in_left+len_left-1,post_left,post_left+len_left-1);
        root->right=dfs(inorder,postorder,in_left+len_left+1,in_right,post_left+len_left,post_right-1);
        return root;
    }
public:
    TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
   
        int len=inorder.size();
        for(int i=0;i<len;++i)
            mp[inorder[i]]=i;
        return dfs(inorder,postorder,0,len-1,0,len-1);
    }
};