[OJ report] binary tree right side view

https://leetcode.com/problems/binary-tree-right-side-view/

The solution is atÂ solution @ github .

The idea is to use DFS to do pre-order traversal of the mirror tree. At the same time, use an array to mark current level, so that we can keep from putting wrong element into the result vector.

```class Solution {
public:
void Helper( TreeNode * root, vector<int> & result,
int cur, vector<int> & marked ){
if(root == NULL) return;
// pre-order of the mirror binary tree
// (DFS & just by swapping the traversal order)
if( result.size() == cur ){
// maintain a marked vector to keep from putting
// wrong element into the result vector
result.push_back(root->val);
}
Helper(root->right, result , cur+1, marked);
Helper(root->left , result , cur+1, marked);
}
vector<int> rightSideView(TreeNode * root){
vector<int> result, marked;
if(root == NULL) return result;
Helper(root, result, 0, marked);
return result;
}
};
```

The runtime complexity is $O(n)$, where $n$ is the node number.

The worst-case memory complexity is $O(n) = O(n)$.

Advertisements