题目题意分析代码 广度搜索先序遍历

题目

Given a binary tree, imagine yourself standing on the right side of it, return the values of the nodes you can see ordered from top to bottom.

For example: Given the following binary tree,

1 <--- / \ 2 3 <--- \ \ 5 4 <---

You should return [1, 3, 4].

题意

给定一个二叉树，想象你自己站在它的右侧，返回从顶部到底部可以看到的节点的值。

例如： 给定以下二叉树，

1 <--- / \ 2 3 <--- \ \ 5 4 <---

应该返回 [1, 3, 4]。

分析

这道题其实很简答，我用的是广度搜索，用一个vector存储一层的node，每一层的最后一个node组成的数组就是我们要的答案。 这个办法的时间复杂度为O(n)，空间复杂度为O(logn)。

小编对比了一下别的做法，看到有用先序遍历的做法，感觉这种办法更好些，其时间复杂度为O(n)，空间复杂度为O(1)；

代码

广度搜索：

210 / 210 test cases passed. Runtime: 3 ms

vector<int> rightSideView(TreeNode* root) { vector<int> result; if(root == NULL) return result; vector<TreeNode*> curr,next; curr.push_back(root); while(true){ if(curr.size()<=0) break; result.push_back(curr.back()->val); for(int i=0;i<curr.size();i++){ if(curr[i]->left) next.push_back(curr[i]->left); if(curr[i]->right) next.push_back(curr[i]->right); } curr = next; next.clear(); } return result; }

先序遍历

210 / 210 test cases passed. Runtime: 3 ms

void preoder(TreeNode *root, int level, vector<int> &res) { if(root==NULL) return ; if(res.size()<level) res.push_back(root->val); preoder(root->right, level+1, res); preoder(root->left, level+1, res); } vector<int> rightSideView(TreeNode *root) { vector<int> res; preoder(root, 1, res); return res; }