199. Binary Tree Right Side View
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.
For example:
Given the following binary tree,
1 <---
/ \
2 3 <---
\ \
5 4 <---
You should return [1, 3, 4].
Credits:
Special thanks to @amrsaqr for adding this problem and creating all test cases.
题解：
输入一个二叉树，从右侧观察二叉树，将观察到的节点从上到下的顺序输出；
分析题目，能够看出，如果我们从右侧观察二叉树；那么能够观察到的节点一定是该二叉树每层的最右边的节点；那么，我们只需要对二叉树宽度优先搜索的时候，存入节点及节点所在的层数，就不难求出每层最右边的节点；
二叉树的宽度优先搜索：https://www.jianshu.com/p/9a0f3e29b479
层次遍历的时候如何将节点和节点所在层数同时存在队列（queue）中呢？
我们想到了STL的另一个容器：对组（pair）；
对组功能：将一对值合成一个值，且这对值可以是任意数据类型；
本题我们要用对组存储二叉树节点和该节点所在层数；
所以：pair<TreeNode *, int> p;
两个值分别用 pair 的 first 和 second 访问：
p.first 表示二叉树节点 root；
p.second : 表示节点所在层数 level；
初始化一个pair可以使用构造函数，也可以使用std::make_pair函数；
std::make_pair(root, level);
好了，在我们能够把二叉树节点和对应的层数同时保存以后，我们就可以愉快地对二叉树宽度优先搜索，然后搜索过程中存入每一层的最后出现的节点的值啦；
对二叉树宽度优先搜索需要借助队列实现，队列存入每次搜索后得到的二叉树节点和节点层数；所以要将对数放入队列中进行层次遍历；
所以最终的声明为：queue<pair<TreeNode *, int>> q;
定义一个vector数组（vector<int> node_val）
用它来存储每层的最右节点值 node_val [level] ；
level = q.front().second；
能够发现，我们只需要不断的更新node_val [level] 的值，就可以得到层次遍历时，在第 level层中最后搜索到的节点（最右边的节点）；
层次遍历结束后得到的 vector 即为从右侧观察二叉树观察到的从上到下顺序输出的节点；
My Solution(C/C++)
#include <cstdio>
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
class Solution {
public:
//vector<pair<int, int>> rightSideView(TreeNode *root) {
vector<int> rightSideView(TreeNode *root) {
queue<pair<TreeNode *, int>> q;
//vector<pair<int, int>> result;
vector<int> node_val;
if (!root) {
return node_val;
}
int level = 0;
q.push(make_pair(root, level));
node_val.push_back(root->val);
while (!q.empty()) {
if (q.front().first->left) {
level += 1;
q.push(make_pair(q.front().first->left, q.front().second + 1));
}
if (q.front().first->right) {
level += 1;
q.push(make_pair(q.front().first->right, q.front().second + 1));
}
if (node_val.size() < q.front().second + 1) {
node_val.push_back(q.front().first->val);
}
if(node_val.size() == q.front().second + 1){
node_val.pop_back();
node_val.push_back(q.front().first->val);
}
//result.push_back(make_pair(q.front().first->val, q.front().second));
q.pop();
}
return node_val;
//return result;
}
};
int main() {
TreeNode a(5);
TreeNode b(4);
TreeNode c(8);
TreeNode d(11);
TreeNode e(13);
TreeNode f(4);
TreeNode g(7);
TreeNode h(2);
TreeNode i(5);
TreeNode j(1);
a.left = &b;
b.left = &d;
d.left = &g;
d.right = &h;
a.right = &c;
c.left = &e;
c.right = &f;
f.left = &i;
f.right = &j;
Solution s;
//vector<pair<int, int>> result;
//result = s.rightSideView(&a);
vector<int> result;
result = s.rightSideView(&a);
for (int i = 0; i < result.size(); i++) {
printf("%d->", result[i]);
}
return 0;
}
结果
5->8->4->1->
My Solution(Python)
import queue
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution(object):
def rightSideView(self, root):
"""
:type root: TreeNode
:rtype: List[int]
"""
if not root:
return []
Q = queue.Queue()
level = 0
val = []
Q.put([root, level])
while not Q.empty():
root, level = Q.get()
if root.left:
Q.put([root.left, level + 1])
if root.right:
Q.put([root.right, level + 1])
val.append(root.val)
val[level] = root.val
return val[:level + 1]
