题解 | #输出二叉树的右视图#
输出二叉树的右视图
https://www.nowcoder.com/practice/c9480213597e45f4807880c763ddd5f0
重构二叉树的代码此处不多赘述。
输出右视图用的也是层序遍历，将下一层的孩子节点先都缓存到另一个队列里，等本层的父节点都处理完了再将孩子节点从缓存队列倒到新队列里来。
这样的话，主队列为空的时候，就代表本层处理完了——也就是说刚处理了本层最右边的节点。借此我们就可以得到二叉树中最右边的节点了。
vector<int> solve(vector<int>& xianxu, vector<int>& zhongxu) {
// write code here
TreeNode* root=reConstructBinaryTree(xianxu, zhongxu);
vector<int>result;
if(root==NULL)
return result;
queue<TreeNode*>Bqueue;
queue<TreeNode*>Childq;
Bqueue.push(root);
//result.push_back(root->val);
while(!Bqueue.empty())
{
TreeNode* Current=Bqueue.front();
Bqueue.pop();
if(Current->left)
Childq.push(Current->left);
if(Current->right)
Childq.push(Current->right);
//说明此时的节点就是这一层的最后一个节点了。
if(Bqueue.empty())
{
result.push_back(Current->val);
while(!Childq.empty())
{
Bqueue.push(Childq.front());
Childq.pop();
}
}
}
return result;
}
查看25道真题和解析