[数据结构与算法]leetcode199. Binary Tree Right Side View

题目：题目链接

思路：题目大意是二叉树的右视图。翻译一下就是记录二叉树每层最右边的结点，所以答案数组的长度肯定是二叉树的高度，因为每层挑一个嘛。肯定要遍历树嘛，那两种方法dfs，bfs。

方法一 dfs

根据我们翻译的内容，对于一个父结点肯定是要先访问左子树，再访问右子树的。然后判断一下当前结点是否加入答案，判断方式就是我们前面提到的，每层只加入一个，所以只要和目前答案数组的长度与高度相比较就可以了。看代码吧：

/**
 * 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:
	void dfs(TreeNode* root, vector<int>& ans, int level) {
		if (root == nullptr) return;
		if (ans.size() == level) ans.push_back(root->val);
		dfs(root->right, ans, level + 1);
		dfs(root->left, ans, level + 1);
	}
	vector<int> rightSideView(TreeNode* root) {
		vector<int>ans;
		dfs(root, ans, 0);
		return ans;
	}
};

方法二 bfs

首先bfs肯定要队列嘛，然后我们按层来拓展结点。和层次遍历稍有不同，我们先访问父节点的右子结点，再访问左子结点。最后对于每一层的第一个结点，我们加入答案(因为我们是先右再左，该层的第一个结点就是最右端的结点)。看代码吧：

/**
  * 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:
	void bfs(TreeNode* root, vector<int>& ans) {
		if (root == nullptr) return;
		queue<TreeNode*>q;
		q.push(root);
		while (!q.empty()) {
			int cnt = q.size();//当前队列的大小其实就是当前层的结点个数
			for (int i = 0; i < cnt; ++i) {//一层一层遍历
				auto tmp = q.front();
				if (i == 0) ans.push_back(tmp->val);//加入第一个
				if (tmp->right) q.push(tmp->right);//先右再左
				if (tmp->left) q.push(tmp->left);
				q.pop();
			}
		}
	}
	vector<int> rightSideView(TreeNode* root) {
		vector<int>ans;
		bfs(root, ans);
		return ans;
	}

搞定了，这题有点意思的。
加油加油加油加油！！！加油加油，你一定可以的！！