给定一棵二叉树,采用广度优先搜索 (BFS) 算法,返回右视图所有节点的值。其中右视图定义为:二叉树的右视图是从树的右侧看过去时可见的节点集合,即右视图中的每个节点都是某一层中最右侧的节点。
struct TreeNode {
int val ;
TreeNode * left ;
TreeNode * right ;
TreeNode ( int x ): val ( x ), left ( nullptr ), right ( nullptr ) {}
};
vector < int > rightSideView ( TreeNode * root ) {
unordered_map < int , int > rightmostValueAtDepth ;
int max_depth = - 1 ;
queue < TreeNode *> nodeQueue ;
queue < int > depthQueue ;
nodeQueue . push ( root );
depthQueue . push ( 0 );
while ( ! nodeQueue . empty ()) {
TreeNode * node = nodeQueue . front (); nodeQueue . pop ();
int depth = depthQueue . front (); depthQueue . pop ();
if ( node != NULL ) {
max_depth = max ( max_depth , depth );
rightmostValueAtDepth [ depth ] = node -> val ;
nodeQueue . push ( node -> left );
nodeQueue . push ( node -> right );
depthQueue . push ( ________ );
depthQueue . push ( ________ );
}
}
vector < int > rightView ;
for ( int depth = 0 ; ________ ; ++ depth ) {
rightView . push_back ( rightmostValueAtDepth [ depth ]);
}
return rightView ;
}
1 depth 2 depth 3 depth < max_depth
1 depth + 1 2 depth + 1 3 depth <= max_depth
1 depth + 1 2 depth + 1 3 depth < max_depth
1 depth 2 depth 3 depth <= max_depth