Right side view of a binary tree using BFS


  • 0
    H

    Problem link is here : https://leetcode.com/problems/binary-tree-right-side-view/description/

    This approach uses a simple breath first search, although this problem can be solved with DFS with just as much simplicity. What we can do is a simple level order traversal and whenever the level changes, we can add the last element to our result vector.

    
    struct SE   // Queue Element
    {
      TreeNode* n;
        int l;
        SE(TreeNode* in, int il) {n=in; l=il;}
    };
    
    class Solution {
    public:
        vector<int> rightSideView(TreeNode* root) {
            
            vector<int> re;
            if (!root) return re;
            
            queue<SE> q; q.push(SE(root, 0));
            
            int curl = 0;
            int preval = 0;
            
            while(q.size()!=0) { 
                
                SE se = q.front();
                
                q.pop();
                
                if (!se.n) continue;
                
                if (curl != se.l) {
                    re.push_back(preval);
                }
                
                curl = se.l;
                preval = se.n->val;
                
                
                q.push(SE(se.n->left, se.l+1)); q.push(SE(se.n->right, se.l+1));
            
            }
            
            re.push_back(preval);
            
            return re;
        }
        
    };
    

Log in to reply
 

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