My C++ solution, modified preorder traversal


  • 89
    G
    class Solution {
    public:
        void recursion(TreeNode *root, int level, vector<int> &res)
        {
            if(root==NULL) return ;
            if(res.size()<level) res.push_back(root->val);
            recursion(root->right, level+1, res);
            recursion(root->left, level+1, res);
        }
        
        vector<int> rightSideView(TreeNode *root) {
            vector<int> res;
            recursion(root, 1, res);
            return res;
        }
    };

  • 3
    S

    if(res.size()<level) ... This is brilliant! :)


  • 0
    Q

    Exactly! if(res.size()<level) is great!


  • 0
    S

    It's a clever solution!! Adding right node first at each level.


  • 0
    Z

    aha,I see what modified means now, root right then left.


  • 0
    C

    awesome solution!!!


  • 0
    L

    it's concise and beautiful. Brilliant solution.


  • 0
    L

    wow , this solution is so nice


  • 0
    H

    if(res.size()<level) good idea


  • 3

    This solution still traverses all nodes of the tree, like the BFS solution, but BFS needs to maintain a queue buffer to store each level's nodes, while this solution only needs res buffer


  • 0
    S

    I think this is actually another way of preorder traversal. The only difference is that this algorithm traverse the right node first.


  • 0
    C

    Suppose n is the number of nodes.
    Space complexity O(logn) for stack frame during recursion.
    Time complexity is O(n) because it still visits all nodes.


  • 1
    B

    Could somebody please help me understand:

    if(res.size()<level)?
    

    Thank you! :)


  • 0
    D

    @BatCoder every level can only have one right side value.


  • 0
    S

    simple level traversal

    class Solution {
    public:
        vector<int> rightSideView(TreeNode* root) {  
            if(!root)
                return vector<int>();
            queue<TreeNode*> inque,outque;
            outque.push(root);
            queue<TreeNode*>& ref_outque = outque;//optimize it without memory copy
            vector<int> res;
            while(!ref_outque.empty())
            {
                TreeNode* tem = ref_outque.front();
                ref_outque.pop();
                if(tem->left) inque.push(tem->left);
                if(tem->right) inque.push(tem->right);
                if(ref_outque.empty())
                {
                    res.push_back(tem->val);   //right side
                    ref_outque = inque;
                    inque = queue<TreeNode*>();
                }
            }
            return res;
        }
    };

  • 0
    B

    @DaGgER14 Yes, I get why he has done that; but I didn't fully understand how checking the size of the vector denotes the level. Could you please elaborate with some examples?


  • 0
    A

    @gavin5 But at the time submission it gives error void declare the recursion .. please help


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.