网站开发项目描述,网页开发三件套,贵阳网站搜索优化,网站跟app区别Problem: 199. 二叉树的右视图 文章目录 题目描述思路解题方法复杂度Code 题目描述 思路
无论是DFS还是BFS我们都要思考到达二叉树的每一层#xff08;或者每一层中的每一个节点#xff09;时#xff0c;我们都该如何按题目要求做出对应得处理!!!在本体中我们主要是#x… Problem: 199. 二叉树的右视图 文章目录 题目描述思路解题方法复杂度Code 题目描述 思路
无论是DFS还是BFS我们都要思考到达二叉树的每一层或者每一层中的每一个节点时我们都该如何按题目要求做出对应得处理!!!在本体中我们主要是 1.当右子树与左子树等高或者右子树高于左子树时我们只添加每一个右子树得右节点到结果集根节点得左子树整个都去除 2.当左子树高于右子树时我们将等高得部分按1中处理左子树高出右子树得部分再将其右子树得右节点添加到结果集 解题方法
思路1DFS 1.创建unordered_mapint, int rightmostValueAtDepth;记录每一层应该添加到右视图的节点int maxDepth -1;记录并维护当前的最大深度stackTreeNode nodeStack;用于DFS过程中的存储节点stack depthStack;用于同时记录DFS过程中的树的深度 2.将根节点添加到nodeStack中while循环遍历循环退出条件为nodeStack为空每次弹出nodeStack和depthStack中的栈顶元素node与depth若此时node不为空则更新最大深度同时若rightmostValueAtDepth[depth]不存在则添加到rightmostValueAtDepth中*并且将node - left;node - rightdepth 1;depth 1分别添加到对应的nodeStack和depthStack栈 3.最后将rightmostValueAtDepth中的值添加到一个一维数组中即可 思路2BFS 大体实现直接套用BFS代码的模板书写即可具体解释下面代码实现中的两个点 1.由于常规的BFS模板均是先添加左子树节点到队列再添加右子树节点到队列所以我们可以利用数组元素可以覆盖的特性在每次添加节点到队列时也将该节点值放入一个空间大小为1的数组temp中这样操作后无论是思路中1、2哪种情况都能保证最后添加到结果集中的节点值是复合题目右视图这个定义 2.按常规BFS代码的实现或者说就是按下面代码前面部分的操作会导致最后一个被写到temp数组中的元素会添加两次到最终的结果集中所以要push_back一次!!! 复杂度
思路1、2均如下 时间复杂度: O ( n ) O(n) O(n) 空间复杂度: O ( n ) O(n) O(n) Code
思路1
class Solution {
public:/*** DFS** param root The root of a binary tree* return vectorint*/vectorint rightSideView(TreeNode *root) {if (root nullptr) {return {};}unordered_mapint, int rightmostValueAtDepth;int maxDepth -1;stackTreeNode * nodeStack;stackint depthStack;nodeStack.push(root);depthStack.push(0);while (!nodeStack.empty()) {TreeNode *node nodeStack.top();nodeStack.pop();int depth depthStack.top();depthStack.pop();if (node ! nullptr) {//Maintain the maximum depth of a binary treemaxDepth max(maxDepth, depth);//If not in the map collection, add itif (rightmostValueAtDepth.find(maxDepth) rightmostValueAtDepth.end()) {rightmostValueAtDepth[depth] node-val;}nodeStack.push(node-left);nodeStack.push(node-right);depthStack.push(depth 1);depthStack.push(depth 1);}}vectorint res;for (int i 0; i maxDepth; i) {res.push_back(rightmostValueAtDepth[i]);}return res;}
};
思路2
class Solution {
public:/*** BFS* * param root The root of a binary tree* return vectorint*/vectorint rightSideView(TreeNode* root) {if (root nullptr) {return {};}if (root - left nullptr root - right nullptr) {return {root - val};}vectorint res;vectorint temp(1);queueTreeNode* queue;res.push_back(root - val);queue.push(root);while (!queue.empty()) {int curLevelSize queue.size();for (int i 0; i curLevelSize; i) {TreeNode* curLevelNode queue.front();queue.pop();if (curLevelNode - left ! nullptr) {temp[0] curLevelNode - left - val;queue.push(curLevelNode - left);}if (curLevelNode - right ! nullptr) {temp[0] curLevelNode - right - val;queue.push(curLevelNode - right);}}res.push_back(temp[0]);}//Pop the last repetitive noderes.pop_back();return res;}
};
