题目描述:
给定一个二叉树的 根节点 root,想象自己站在它的右侧,按照从顶部到底部的顺序,返回从右侧所能看到的节点值。
输入: [1,2,3,null,5,null,4] 输出: [1,3,4]
一、DFS实现
思路:
从根部开始向右搜索,定义一个step表示层数,从0开始,再定义一个vector容器res储存每一层的最右边的元素,直到最底层的最右边元素添加到res中。
代码:
class Solution { public: vector<int> res; vector<int> rightSideView(TreeNode* root) { dfs(root,0); //从根部开始 return res; } void dfs(TreeNode* root,int step){ if(root==nullptr){ return ; } if(step==res.size()){ res.push_back(root->val); //每一层的最后边的元素加入到容器中 } dfs(root->right,step+1); //继续向右搜索 dfs(root->left,step+1); //右边到达叶子节点时向左边搜索 } };
二、层序遍历实现
1.思路:
根据层序遍历的思想,每遍历一层的最右边的元素就是右视图中的元素。
2.代码:
class Solution { public: vector<int> rightSideView(TreeNode* root) { vector<int> res; //储存符合条件的元素 queue<TreeNode*> que; //队列实现层序遍历 if(root!=nullptr){ //先将根节点加入队列 que.push(root); } while(!que.empty()){ int size=que.size(); //一定要把队列大小赋值给常量,因为队列大小在循环中一直会变化 for(int i=0;i<size;i++){ TreeNode* node=que.front(); que.pop(); //出队列 if(i==(size-1)){ //把每一层层序遍历的最后一个元素加入到容器中 res.push_back(node->val); } if (node->left!=nullptr){ que.push(node->left); } if (node->right!=nullptr){ que.push(node->right); } } } return res; } };