NC223. 从中序与后序遍历序列构造二叉树
描述
示例1
输入:
[1],[1]
输出:
{1}
示例2
输入:
[2,1,4,3,5],[2,4,5,3,1]
输出:
{1,2,3,#,#,4,5}
C++ 解法, 执行用时: 3ms, 内存消耗: 408KB, 提交时间: 2022-04-13
/**
* struct TreeNode {
* int val;
* struct TreeNode *left;
* struct TreeNode *right;
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* };
*/
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param inorder int整型vector 中序遍历序列
* @param postorder int整型vector 后序遍历序列
* @return TreeNode类
*/
TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
// write code here
if(inorder.empty())
return nullptr;
int istart=0,iend=inorder.size()-1,pstart=0,pend=postorder.size()-1;
int index=0;
TreeNode* root=new TreeNode(postorder[pend]);
for(int i=0;i<inorder.size();++i)
{
if(postorder[pend]==inorder[i])
{
index=i;
break;
}
}
if(index-1>=istart&&pstart+index-istart-1>=pstart)
root->left=buildTreecore(inorder,postorder,istart,index-1,pstart,pstart+index-istart-1);
if(iend>=index+1&&pend-1>=pstart+index-istart)
root->right=buildTreecore(inorder,postorder,index+1,iend,pstart+index-istart,pend-1);
return root;
}
TreeNode* buildTreecore(vector<int>& inorder,vector<int>& postorder,int istart,int iend,int pstart,int pend)
{
if(istart>iend||pstart>pend)
return nullptr;
TreeNode* root=new TreeNode(postorder[pend]);
int index=0;
for(int i=istart;i<=iend;++i)
{
if(postorder[pend]==inorder[i])
{
index=i;
break;
}
}
if(index-1>=istart&&pstart+index-istart-1>=pstart)
root->left=buildTreecore(inorder,postorder,istart,index-1,pstart,pstart+index-istart-1);
if(iend>=index+1&&pend-1>=pstart+index-istart)
root->right=buildTreecore(inorder,postorder,index+1,iend,pstart+index-istart,pend-1);
return root;
}
};
C++ 解法, 执行用时: 3ms, 内存消耗: 408KB, 提交时间: 2021-12-25
// https://www.nowcoder.com/practice/ab8dde7f01f3440fbbb7993d2411a46b?tpId=117
// 根据后序变量获得根坐标，再从中序遍历划分左右半区
/**
* struct TreeNode {
* int val;
* struct TreeNode *left;
* struct TreeNode *right;
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* };
*/
class Solution {
public:
TreeNode* buildTree(vector<int> &inorder, vector<int> &postorder) {
TreeNode *root = nullptr;
int n = inorder.size();
root = dfs(inorder, postorder, 0, n-1, 0, n-1);
return root;
}
TreeNode* dfs(vector<int> &nums1, vector<int> &nums2, int l1, int r1, int l2, int r2) {
if(l1 > r1 || l2 > r2) return nullptr; // 重要
if(l1 == r1) return new TreeNode(nums1[l1]); // 中序只有一个元素,重要
int k, temp;
int elem_val = nums2[r2];
TreeNode *root = new TreeNode(elem_val);
for(k = l1; k <= r1; k++) {
if(nums1[k] == elem_val) break;
}
temp = r2 - (r1 - k);
root->left = dfs(nums1, nums2, l1, k-1, l2, temp-1);
root->right = dfs(nums1, nums2, k+1, r1, temp, r2-1);
return root;
}
};
/*
[2,1,4,3,5],[2,4,5,3,1]
[1,2,3,#,#,4,5]
[4,2,5,1,6,3,7],[4,5,2,6,7,3,1]
[1,2,3,4,5,6,7]
[5,4,3,2,1],[5,4,3,2,1]
[1,2,#,3,#,4,#,5]
*/
C++ 解法, 执行用时: 3ms, 内存消耗: 412KB, 提交时间: 2022-04-05
/**
* struct TreeNode {
* int val;
* struct TreeNode *left;
* struct TreeNode *right;
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* };
*/
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param inorder int整型vector 中序遍历序列
* @param postorder int整型vector 后序遍历序列
* @return TreeNode类
*/
TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
// write code here
return MyTree(inorder, 0, inorder.size(), postorder, 0, postorder.size());
}
TreeNode* MyTree (vector<int>& inorder, int inorderBegin, int inorderEnd, vector<int>& postorder, int postorderBegin, int postorderEnd) {
if (postorderBegin == postorderEnd) return NULL;
int rootValue = postorder[postorderEnd - 1];
TreeNode* root = new TreeNode(rootValue);
if (postorderEnd - postorderBegin == 1) return root;
int delimiterIndex;
for (delimiterIndex = inorderBegin; delimiterIndex < inorderEnd; delimiterIndex++) {
if (inorder[delimiterIndex] == rootValue) break;
}
// 切割中序数组
// 左中序区间，左闭右开[leftInorderBegin, leftInorderEnd)
int leftInorderBegin = inorderBegin;
int leftInorderEnd = delimiterIndex;
// 右中序区间，左闭右开[rightInorderBegin, rightInorderEnd)
int rightInorderBegin = delimiterIndex + 1;
int rightInorderEnd = inorderEnd;
// 切割后序数组
// 左后序区间，左闭右开[leftPostorderBegin, leftPostorderEnd)
int leftPostorderBegin = postorderBegin;
int leftPostorderEnd = postorderBegin + delimiterIndex - inorderBegin; // 终止位置是 需要加上 中序区间的大小size
// 右后序区间，左闭右开[rightPostorderBegin, rightPostorderEnd)
int rightPostorderBegin = postorderBegin + (delimiterIndex - inorderBegin);
int rightPostorderEnd = postorderEnd - 1; // 排除最后一个元素，已经作为节点了
root->left = MyTree(inorder, leftInorderBegin, leftInorderEnd, postorder, leftPostorderBegin, leftPostorderEnd);
root->right = MyTree(inorder, rightInorderBegin, rightInorderEnd, postorder, rightPostorderBegin, rightPostorderEnd);
return root;
}
};
C++ 解法, 执行用时: 3ms, 内存消耗: 412KB, 提交时间: 2021-12-14
/**
* struct TreeNode {
* int val;
* struct TreeNode *left;
* struct TreeNode *right;
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* };
*/
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param inorder int整型vector 中序遍历序列
* @param postorder int整型vector 后序遍历序列
* @return TreeNode类
*/
TreeNode* buildTree(vector<int>& inorder,vector<int>& postorder, int& pos, int left, int right) {
if (pos < 0) return 0;
TreeNode* root = new TreeNode(postorder[pos]);
int i;
for (i = left; i <= right; i++) {
if (inorder[i] == postorder[pos]) break;
}
if (i + 1 <= right) root->right = buildTree(inorder, postorder, --pos, i + 1, right);
if (i - 1 >= left) root ->left = buildTree(inorder, postorder, --pos, left, i - 1);
return root;
}
TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
// write code here
int pos = postorder.size() - 1;
return buildTree(inorder, postorder, pos, 0, postorder.size() - 1);
}
};
C++ 解法, 执行用时: 3ms, 内存消耗: 416KB, 提交时间: 2021-12-02
/**
* struct TreeNode {
* int val;
* struct TreeNode *left;
* struct TreeNode *right;
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* };
*/
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param inorder int整型vector 中序遍历序列
* @param postorder int整型vector 后序遍历序列
* @return TreeNode类
*/
TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
// write code here
return dfs(inorder, postorder, 0, inorder.size() - 1, 0, postorder.size() - 1);
}
TreeNode* dfs(vector<int>& inorder, vector<int>& postorder, int inl, int inr, int postl, int postr){
if(postl > postr) return nullptr;
int index = 0, target = postorder[postr];
TreeNode* newNode = new TreeNode(target);
for(index = inl; index <= inr; index++)
if(inorder[index] == target) break;
newNode -> left = dfs(inorder, postorder, inl, index - 1, postl, postl + index - inl - 1);
newNode -> right = dfs(inorder, postorder, index + 1, inr, postl + index - inl, postr - 1);
return newNode;
}
};