199. Binary Tree Right Side View

发表于 | 分类于 | 阅读次数
字数统计 240 | 阅读时长 1

Given a binary tree, imagine yourself standing on the right side of it, return the values of the nodes you can see ordered from top to bottom.

1
2
3
4
5
6
7
8
9
For example:
Given the following binary tree,

   1            <---
 /   \
2     3         <---
 \     \
  5     4       <---
You should return [1, 3, 4].

题意：

　　给定一棵二叉树，返回从右边看这棵二叉树所看到的节点序列（从上到下）。

思路：

　　层次遍历法，遍历到每层最后一个节点时，把其放到结果集中。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
class Solution {
public:
	vector<int> rightSideView(TreeNode* root) {
		vector<int> res;
		if (!root)
			return res;
		queue<TreeNode*> que1;
		que1.push(root);
		while (!que1.empty())
		{
			queue<TreeNode*> que2;
			while (!que1.empty()) {
				TreeNode* temp = que1.front();
				que1.pop();
				if (temp->left)
				{
					que2.push(temp->left);
				}
				if (temp->right)
				{
					que2.push(temp->right);
				}
				if (que1.empty())
				{
					res.push_back(temp->val);//取最右边元素放入结果集
				}
			}
			que1 = que2;
		}
		return res;
	}
};