[recommend for beginners]clean C++ implementation with detailed explanation


  • 2

    My first implementation is as follows, as you can see , my consideration loses some cases.

    When the right-sub-tree-sub-tree is NULL then MY Implementation can not return the correct results.

    class Solution {
    public:
        vector<int> rightSideView(TreeNode* root) {
            vector<int> result;
            help(root, result);
            return result;
        }
        
        void help(TreeNode* root, vector<int>& result){
            if(!root)   return;
            result.push_back(root->val);
            if(root->right)   help(root->right, result);
            else if(root->left)  help(root->left, result);
            else return;
        }
    };
    

    To fix this problem , I refered to others' posts, as you can see, I add a int-variable-to check the current

    level node whether has been added. IF not, just add it. IF added, then we can reject add the left-sub-

    tree-node by checking the level

       class Solution {
        public:
            vector<int> rightSideView(TreeNode* root) {
                vector<int> result;
                help(root, result, 1);
                return result;
            }
            
            void help(TreeNode* root, vector<int>& result, int level){
                if(!root)   return;
                if(result.size() < level) result.push_back(root->val);
                help(root->right, result, level+1);
                help(root->left, result, level+1);
            }
        };

  • 0
    C

    Thanks a lot, I made same mistake~


  • 0
    N

    Hi , could you explain me this level variable little in depth? Thank you.


  • 0

    @naveen15 You can think that we use the level to check whether have push_back a new node from the right, if not , then we will push_back the same level node from left tree.

    Do you get what I mean ?


  • 0
    N

    Yes this made it clear, Thank you very much :).


  • 0
    2

    This problem is harder than I think

    In my second try..... 3 TIME ac..........

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

  • 0
    F

    Here is a non-recursive solution refered to the level by level traversal of the tree structure :

    class Solution {
    public:
        vector<int> rightSideView(TreeNode* root) {
            deque<TreeNode*> dq;
            vector<int> result;
            if (!root)  return result;
            dq.push_back(root);
            while (!dq.empty()) {
                result.push_back(dq.back()->val);
                for (int i = dq.size(); i > 0; i--) {
                    TreeNode* cur = dq.front();
                    dq.pop_front();
                    if (cur->left)  dq.push_back(cur->left);
                    if (cur->right) dq.push_back(cur->right);
                }
            }
            return result;
        }
    };

Log in to reply
 

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