① bfs 层序遍历:记录每一层的最后一个节点即可
② dfs,与先序遍历相反,先遍历右节点,这样就是当前层次第一个出现的数就是最右边的数。
// bfs 代码
class Solution { public: vector<int> rightSideView(TreeNode* root) { vector<int> ret; queue<pair<TreeNode*, int>> que; if(root) que.push({root, 1}); while(!que.empty()) { auto front = que.front(); que.pop(); if(front.second == ret.size()) { ret.back() = front.first -> val; } else { ret.push_back(front.first -> val); } if(front.first -> left) { que.push({front.first -> left, front.second + 1}); } if(front.first -> right) { que.push({front.first -> right, front.second + 1}); } } return ret; } };