106. 從中序與后序遍歷序列構造二叉樹

給定兩個整數數組?inorder?和?postorder?，其中?inorder?是二叉樹的中序遍歷，?postorder?是同一棵樹的后序遍歷，請你構造并返回這顆?二叉樹?。

示例 1:

輸入：inorder = [9,3,15,20,7], postorder = [9,15,7,20,3]
輸出：[3,9,20,null,null,15,7]

示例 2:

輸入：inorder = [-1], postorder = [-1]
輸出：[-1]

提示:

• 1 <= inorder.length <= 3000
• postorder.length == inorder.length
• -3000 <= inorder[i], postorder[i] <= 3000
• inorder?和?postorder?都由?不同?的值組成
• postorder?中每一個值都在?inorder?中
• inorder?保證是樹的中序遍歷
• postorder?保證是樹的后序遍歷

/*** 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 {
public:TreeNode* make_tree(vector<int>& inorder, vector<int>& postorder){//首要就是看后序遍歷的節點來找根節點劃分if(postorder.size()==0)return nullptr;int temp=postorder[postorder.size()-1];TreeNode* root=new TreeNode(temp);//這就是當中的根節點// 葉子節點if (postorder.size() == 1) return root;//重塑postorder的大小，刪除最后一個節點postorder.resize(postorder.size() - 1);//開始劃分中序遍歷int i=0;for(i=0;i<inorder.size();i++){if(inorder[i]==temp)break;//找到劃分的界限}vector<int>in_left(inorder.begin(),inorder.begin()+i);vector<int>in_right(inorder.begin()+i+1,inorder.end());//要知道即便是劃分后，對應的各自中后序遍歷都是大小相同的vector<int>po_left(postorder.begin(),postorder.begin()+in_left.size());vector<int>po_right(postorder.begin()+in_left.size(),postorder.end());//這里有個易錯點，postorder.begin()+in_left.size()//而不是postorder.begin()+in_left.size()+1   因為你不需要想中序遍歷那樣跳過中間那個節點root->left=make_tree(in_left,po_left);root->right=make_tree(in_right,po_right);return root;}TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {if(inorder.size()==0||postorder.size()==0)return nullptr;return make_tree(inorder,postorder);}
};

105. 從前序與中序遍歷序列構造二叉樹

給定兩個整數數組?preorder?和?inorder?，其中?preorder?是二叉樹的先序遍歷，?inorder?是同一棵樹的中序遍歷，請構造二叉樹并返回其根節點。

示例 1:

輸入: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
輸出: [3,9,20,null,null,15,7]

示例 2:

輸入: preorder = [-1], inorder = [-1]
輸出: [-1]

提示:

• 1 <= preorder.length <= 3000
• inorder.length == preorder.length
• -3000 <= preorder[i], inorder[i] <= 3000
• preorder?和?inorder?均?無重復?元素
• inorder?均出現在?preorder
• preorder?保證?為二叉樹的前序遍歷序列
• inorder?保證?為二叉樹的中序遍歷序列

/*** 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 {
public:TreeNode* make_tree(vector<int>& preorder, vector<int>& inorder){if(preorder.size()==0)return nullptr;//這是跳出遞歸的出口int temp=preorder[0];TreeNode* root=new TreeNode(temp);if(preorder.size()==1)return root;//這也是跳出的出口//重塑前序遍歷，把最前面那個刪除，但是這個不好刪，只需要在劃分那里避開第一個值//劃分中序遍歷int i=0;for(i=0;i<inorder.size();i++){if(inorder[i]==temp)break;}vector<int>in_left(inorder.begin(),inorder.begin()+i);vector<int>in_right(inorder.begin()+i+1,inorder.end());//劃分前序遍歷vector<int>pre_left(preorder.begin()+1,preorder.begin()+1+in_left.size());vector<int>pre_right(preorder.begin()+1+in_left.size(),preorder.end());//劃分的時候左閉右開root->left=make_tree(pre_left,in_left);root->right=make_tree(pre_right,in_right);return root;}TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {if(preorder.size()==0||inorder.size()==0)return nullptr;return make_tree(preorder,inorder);}
};