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 , where is the node number.

The worst-case memory complexity is .

### Like this:

Like Loading...

*Related*