题目描述: 给定一棵二叉树,想象自己站在它的右侧,按照从顶部到底部的顺序,返回从右侧所能看到的节点值。
示例:
输入: [1,2,3,null,5,null,4] 输出: [1, 3, 4] 解释:
解题思路 执行用时,内存消耗相差无几
BFS用队列实现。根据队列先进先出的特点,每一层最后一个结点即为最右端点。所以,只需在遍历的同时,获取每一层倒数第一个结点即可。
DFS用非递归栈和set实现。DFS顺序为根右左,也就是说每一层出现的第一个结点即为最右端点。所以,可以用set记录层数来判断该层数是否第一次出现,同时栈的存储类型采用pair数据对存放模拟递归的命令结构体Commend
和当前结点所处层数level
,如果是第一次出现,说明该结点为最右端点。至于非递归实现部分,采用Commend结构体模拟递归时系统栈的运作方式及先后顺序,也就是说“根左右”在系统栈的执行顺序会是“右左根”。
代码 BFS 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 class Solution {public : vector <int > rightSideView(TreeNode* root) { vector <int > result; if (!root) return result; queue <TreeNode*> queue_Tree; queue_Tree.push(root); while (!queue_Tree.empty()){ int n = queue_Tree.size(); for (int i = 0 ; i < n; i++){ TreeNode* node = queue_Tree.front(); queue_Tree.pop(); if (node->left) queue_Tree.push(node->left); if (node->right) queue_Tree.push(node->right); if (i == n - 1 ) result.push_back(node->val); } } return result; } };
DFS 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 struct Commend { string s; TreeNode* node; Commend(string s, TreeNode* node) : s(s), node(node) {} }; class Solution {public : vector <int > rightSideView(TreeNode* root) { vector <int > result; unordered_set <int > record; if (!root) return result; stack <pair<Commend,int >> stack_Tree; stack_Tree.push(make_pair(Commend("go" ,root),0 )); while (!stack_Tree.empty()){ int n = stack_Tree.size(); Commend commend = stack_Tree.top().first; int level = stack_Tree.top().second; stack_Tree.pop(); if (commend.s == "print" ){ result.push_back(commend.node->val); } else { assert(commend.s == "go" ); if (commend.node->left){ stack_Tree.push(make_pair(Commend("go" ,commend.node->left), level + 1 )); } if (commend.node->right){ stack_Tree.push(make_pair(Commend("go" ,commend.node->right), level + 1 )); } if (record.find(level) == record.end()){ record.insert(level); stack_Tree.push(make_pair(Commend("print" ,commend.node), level)); } } } return result; } };
如果有错误或者不严谨的地方,请务必给予指正,十分感谢。