BM41. 输出二叉树的右视图
描述
示例1
输入:
[1,2,4,5,3],[4,2,5,1,3]
输出:
[1,3,5]
C++ 解法, 执行用时: 2ms, 内存消耗: 328KB, 提交时间: 2021-05-26
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
* 求二叉树的右视图
* @param xianxu int整型vector 先序遍历
* @param zhongxu int整型vector 中序遍历
* @return int整型vector
*/
struct TreeNode{
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int x)
{
val=x;
left=NULL;
right=NULL;
}
};
TreeNode * recover(vector<int>& xianxu, vector<int>& zhongxu,int l1,int r1,int l2,int r2)
{
if(l1>r1)
return NULL;
TreeNode *root=new TreeNode(xianxu[l1]);
for(int i=l2;i<=r2;++i)
{
if(root->val==zhongxu[i])
{
root->left=recover(xianxu, zhongxu, l1+1, l1+i-l2, l2, i-1);
root->right=recover(xianxu, zhongxu, l1+i-l2+1, r1, i+1, r2);
}
}
return root;
}
vector<int> solve(vector<int>& xianxu, vector<int>& zhongxu) {
// write code here
TreeNode*root=recover(xianxu, zhongxu, 0, xianxu.size()-1, 0, zhongxu.size()-1);
vector<int> res;
if(root==nullptr)
return res;
queue<TreeNode*> que;
que.push(root);
while(!que.empty())
{
int len=que.size();
for(int i=0;i<len;++i)
{
root=que.front();
if(i==len-1)
res.push_back(root->val);
que.pop();
if(root->left)
{
que.push(root->left);
}
if(root->right)
{
que.push(root->right);
}
}
}
return res;
}
};
C++ 解法, 执行用时: 2ms, 内存消耗: 328KB, 提交时间: 2021-05-15
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
* 求二叉树的右视图
* @param xianxu int整型vector 先序遍历
* @param zhongxu int整型vector 中序遍历
* @return int整型vector
*/
struct TreeNode
{
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int v)
{
val=v;
left=NULL;
right=NULL;
}
};
vector<int>res;
unordered_map<int,int>mmap;
vector<int> solve(vector<int>& xianxu, vector<int>& zhongxu) {
// write code here
for(int i=0;i<xianxu.size();i++)
{
mmap[zhongxu[i]]=i;
}
return youshi(helper(xianxu,zhongxu,0,xianxu.size()-1,0,zhongxu.size()-1));
}
TreeNode *helper(vector<int>& xianxu, vector<int>& zhongxu,int xianxu_left,int xianxu_right,
int zhongxu_left,int zhongxu_right)
{
if(xianxu_left>xianxu_right)
{
return NULL;
}
TreeNode *root=new TreeNode(xianxu[xianxu_left]);
int pos_root=mmap[xianxu[xianxu_left]];
int left_len=pos_root-zhongxu_left;
root->left=helper(xianxu,zhongxu,xianxu_left+1,xianxu_left+left_len,zhongxu_left,pos_root-1);
root->right=helper(xianxu,zhongxu,xianxu_left+left_len+1,xianxu_right,pos_root+1,zhongxu_right);
return root;
}
vector<int> youshi(TreeNode *root)
{
if(root==NULL)
{
return res;
}
queue<TreeNode*>que;
que.push(root);
while(!que.empty())
{
int len=que.size();
for(int i=0;i<len;i++)
{
root=que.front();
if(i==len-1)
{
res.push_back(root->val);
}
que.pop();
if(root->left)
{
que.push(root->left);
}
if(root->right)
{
que.push(root->right);
}
}
}
return res;
}
};
C 解法, 执行用时: 2ms, 内存消耗: 328KB, 提交时间: 2021-03-29
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
* 求二叉树的右视图
* @param xianxu int整型一维数组 先序遍历
* @param xianxuLen int xianxu数组长度
* @param zhongxu int整型一维数组 中序遍历
* @param zhongxuLen int zhongxu数组长度
* @return int整型一维数组
* @return int* returnSize 返回数组行数
*/
int* solve(int* xianxu, int xianxuLen, int* zhongxu, int zhongxuLen, int* returnSize ) {
// write code here
if(!xianxu || !zhongxu){ *returnSize = 0; return NULL; }
struct TreeNode *pTN_stk[xianxuLen]; int idx = 0, i = 1, j = 0, top, cmp;
struct TreeNode *Header = (struct TreeNode *)calloc(1, sizeof(struct TreeNode)), *pHead = Header;
pHead->val = top = xianxu[0]; cmp = zhongxu[0];
pTN_stk[0] = pHead;
while(i < xianxuLen)
{
if(top != cmp){
pHead->left = (struct TreeNode *)calloc(1, sizeof(struct TreeNode));
pHead = pHead->left;
pHead->val = top = xianxu[ i++ ];
pTN_stk[ ++idx ] = pHead;
continue;
}
j++;
while(--idx!=-1 && pTN_stk[idx]->val==zhongxu[j]){
pHead = pTN_stk[idx]; j++;
}
pHead->right = (struct TreeNode *)calloc(1, sizeof(struct TreeNode));
pHead = pHead->right;
pHead->val = top = xianxu[ i++ ]; cmp = zhongxu[j];
pTN_stk[ ++idx ] = pHead;
}
int f_idx = 0, rear_idx = 0, record[xianxuLen], id = 0;
pTN_stk[0] = Header; idx = 0;
while(idx <= rear_idx)
{
while(idx < f_idx)
{
pHead = pTN_stk[ idx++ ];
if(pHead->left) pTN_stk[ ++rear_idx ] = pHead->left;
if(pHead->right) pTN_stk[ ++rear_idx ] = pHead->right;
free(pHead);
}
pHead = pTN_stk[ idx++ ];
if(pHead->left) pTN_stk[ ++rear_idx ] = pHead->left;
if(pHead->right) pTN_stk[ ++rear_idx ] = pHead->right;
record[ id++ ] = pHead->val;
free(pHead);
f_idx = rear_idx;
}
int *res = (int *)malloc( id*sizeof(int) );
memcpy(res, record, id*sizeof(int));
*returnSize = id;
return res;
}
C++ 解法, 执行用时: 2ms, 内存消耗: 328KB, 提交时间: 2020-11-23
struct Node
{
int val;
Node *left;
Node *right;
Node(int x=0):val(x),left(nullptr),right(nullptr){};
};
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
* 求二叉树的右视图
* @param xianxu int整型vector 先序遍历
* @param zhongxu int整型vector 中序遍历
* @return int整型vector
*/
Node* buildTree(vector<int> &pre,vector<int> &mid,int le1,int ri1,int le2,int ri2)
{
if(le1>ri1||le1-ri1!=le2-ri2)
return 0;
int index=le2; //首地址
while(mid[index]!=pre[le1])
{
++index; //在中序遍历中首先寻找根节点（前序的第一个数） 该下标的左边的数为左子树，右边的数位右子树
}
Node *p=new Node(pre[le1]); //前序的第一个数为根节点
p->left=buildTree(pre,mid,le1+1,le1+index-le2,le2,index-1); //卡出前序和中序遍历中的左子树的部分（前后下标值）
p->right=buildTree(pre,mid,le1+index-le2+1,ri1,index+1,ri2); //卡出前序和中序遍历中的右子树的部分（前后下标值）
return p;
}
vector<int> solve(vector<int>& xianxu, vector<int>& zhongxu) {
// write code here
//通过前序和后序重建树结构
Node *head=buildTree(xianxu,zhongxu, 0,xianxu.size()-1,0,zhongxu.size()-1);
//res用以存放右视图的值val
vector<int> res;
if(head==0)
return res;
//队列用以存放树，实现层序遍历
queue<Node*> q;
q.push(head);
while(!q.empty())
{
Node *temp=q.front();
res.push_back(temp->val);
for(int i=q.size();i>0;i--)
{
temp=q.front();
q.pop();
if(temp->right)
q.push(temp->right);
if(temp->left)
q.push(temp->left);
}
}
return res;
}
};
C++ 解法, 执行用时: 2ms, 内存消耗: 328KB, 提交时间: 2020-11-19
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
* 求二叉树的右视图
* @param xianxu int整型vector 先序遍历
* @param zhongxu int整型vector 中序遍历
* @return int整型vector
*/
vector<int> R;
void dfs(vector<int>& xianxu, vector<int>& zhongxu,int j)
{
if(xianxu.size())
{
int key = xianxu[0];
if(R.size()<j)
{
R.push_back(key);
}
vector<int> FL,FR,ML,MR;
int i=0;
while(zhongxu[i]!=key)
{
FL.push_back(xianxu[i+1]);
ML.push_back(zhongxu[i]);
i++;
}
i++;
for(;i<xianxu.size();i++)
{
FR.push_back(xianxu[i]);
MR.push_back(zhongxu[i]);
}
dfs(FR,MR,j+1);
dfs(FL,ML,j+1);
}
}
vector<int> solve(vector<int>& xianxu, vector<int>& zhongxu) {
// write code here
dfs(xianxu,zhongxu,1);
return R;
}
};