首先需要确定树的高度,再利用递归的思想,先遍历右子树,再遍历左子树。
在遍历过程中,要检查当前层是否访问过,以及当前层高度是否等于树高
/**
* 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:
int getHeight(TreeNode* root)
{
int level = 0;
TreeNode* cur;
deque<TreeNode*> queue;
if (root == NULL) return 0;
/* 根节点入队 */
queue.push_back(root);
/* 遍历 */
while (!queue.empty())
{
int size = queue.size();
level++;
for (int i = 0; i < size; i++)
{
cur = queue.front();
queue.pop_front();
if (cur->left != NULL)
queue.push_back(cur->left);
if (cur->right != NULL)
queue.push_back(cur->right);
}
}
return level;
}
vector<int> rightSideView(TreeNode* root)
{
vector<int> res;
int curHeight = 0;
int curMaxHeight = 0;
int height = getHeight(root);
viewFromRight(root, curHeight, curMaxHeight, height, res);
return res;
}
void viewFromRight(TreeNode* root, int& curHeight, int& curMaxHeight, int height, vector<int>& res)
{
if (root == NULL) return;
curHeight++;
//根节点
if (curHeight == 1)
{
curMaxHeight = curHeight;
res.push_back(root->val);
viewFromRight(root->right, curHeight, curMaxHeight, height, res);
viewFromRight(root->left, curHeight, curMaxHeight, height, res);
}
//已完成遍历
else if (curMaxHeight == height)
{
return;
}
//非根节点,且当前层未访问过
else if (curHeight > curMaxHeight)
{
curMaxHeight = curHeight;
res.push_back(root->val);
viewFromRight(root->right, curHeight, curMaxHeight, height, res);
viewFromRight(root->left, curHeight, curMaxHeight, height, res);
}
//非根节点,且当前层访问过
else if (curHeight <= curMaxHeight)
{
viewFromRight(root->right, curHeight, curMaxHeight, height, res);
viewFromRight(root->left, curHeight, curMaxHeight, height, res);
}
curHeight--;
}
};