二叉树bfsdfs-199二叉树的右视图

给定一棵二叉树，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。

在二叉树问题中，递归dfs是很常用的方法，本题同样适用。

 dfs: 分别考虑左右子树的右视图，

        若左子树的右视图的高度>右子树的右视图高度, 则右视图为右子树的右视图+左子树剩余的右视图

        若左子树的右视图的高度>右子树的右视图高度, 则右视图为右子树的右视图

代码(c++)

vector <int> res; if (root==NULL) return res; res.push_back(root->val); vector<int> left_rightView = rightSideView(root->left); vector<int> right_rightView = rightSideView(root->right); for (int i = 0; i<right_rightView.size(); ++i) res.push_back(right_rightView[i]); if (left_rightView.size() > right_rightView.size()) { int n = right_rightView.size(); for (int i = n; i<left_rightView.size(); ++i) res.push_back(left_rightView[i]); } return res;

bfs:  利用层次遍历，输出每一层最后一个节点 

代码(c++)

vector <int> res; if (root==NULL) return res; queue <TreeNode *> qe; qe.push(root); while (!qe.empty()) { int n = qe.size(); for (int i=0; i<n; ++i) { TreeNode* t = qe.front(); if (i==n-1) res.push_back(t->val); qe.pop(); if (t->left) qe.push(t->left); if (t->right) qe.push(t->right); } } return res;