Binary Tree Right Side View

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.

Discussion

level order

1. Each depth of the tree only select one node.

2. View depth is current size of result list.

Solution

class Solution {
public:
    void dfs(TreeNode* root, int lv, vector<int> &res){
        if(!root)   return;
        if(lv>=res.size()) res.push_back(root->val);
        dfs(root->right,lv+1,res);
        dfs(root->left,lv+1,res);
    }

    vector<int> rightSideView(TreeNode* root) {
        vector<int> res;
        dfs(root, 0, res);
        return res;
    }
};

level order traversal， 先右后左，每次去第一个就是最右边的

class Solution {
public:
    vector<int> rightSideView(TreeNode *root) {
        queue<TreeNode*>mQ;
        vector<int> ret;
        if(!root)return ret;
        mQ.push(root);
        while(!mQ.empty()){
            ret.push_back(mQ.front()->val);
            for(int i=mQ.size();i>0;i--){
                TreeNode *tn=mQ.front();
                mQ.pop();
                if(tn->right)mQ.push(tn->right);//先右后左才可以
                if(tn->left)mQ.push(tn->left);
            }
        }
        return ret;
    }
};

两种方法都是O(n) run time. 第一个O(logN) stack space. 第二个O(n)