看到这个题目的一瞬间,我想递归,必须用递归。最近被递归折磨的有点狠,但是我感觉我快要打败它了,就是现在稍稍有点处于劣势。不过没关系,来日方长不是。
法一:递归
题解:
之前想的就是先递归,遍历其右子树,然后将返回的值放到一个栈里面,最后输出栈中的值就可以了,但是后面发现其实没有必要用到栈,只要自己在每一次调用本身之前将之前的值放到一维数组中就可以了。像下面这样!
法二:DFS深度遍历
首先我我知道这个看起来很简单,我也能看懂官方的解答,但是对于读代码的能力还是得有待加强。具体就是我一直觉得depth是结点的个数,然后自己就很努力的在那证明官方的解答是错误的,后来啊~我错了。哈哈哈哈哈。所以depth的值是层数,代码中也并没有很明显的表示depth=多少对吧,眼瞎啊!!!
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
vector<int> rightSideView(TreeNode* root) {
unordered_map<int,int> rightmostValueDepth; //定义一个哈希表,用以表示层数和值的对应关系
int max_depth=-1;
stack<TreeNode*>nodeStack; //用以存储结点的栈
stack<int> depthStack; //用以存储个数 的栈
nodeStack.push(root);
depthStack.push(0);
while(!nodeStack.empty()){
//取出此时栈顶元素
TreeNode *node=nodeStack.top();
nodeStack.pop();
//取出此时树的层数
int depth=depthStack.top();
cout<<depth;
depthStack.pop();
if(node!=NULL){
max_depth=max(max_depth,depth);
if(rightmostValueDepth.find(depth)==rightmostValueDepth.end()){
rightmostValueDepth[depth]=node->val;
}
nodeStack.push(node->left);
nodeStack.push(node->right);
depthStack.push(depth+1);
depthStack.push(depth+1);
}
}
vector<int> rightView;
for(int depth=0;depth<=max_depth;depth++){
rightView.push_back(rightmostValueDepth[depth]);
}
return rightView;
}
};
最后就是也可以用BFS算法,只要把栈换成队列,嗯,差不多了。
今天,我觉得自己的脑子好像一个破烂的水桶,不每天都修修补补的话(我的意思是复习),就还会是原来那样。温故而知新啊~
天天开心哦~
请你喝碗鸡汤
“你要忍,忍到春暖花开;你要走,走到灯火通明;你要看过世界辽阔,再评判是好是坏;你要卯足变好,再旗鼓相当站在不敢想的人身边;你要变成想象中的样子,这件事,一步都不能让”
——卢思浩
加油哦~