Share my Java iterative solution, based on level order traversal


  • 18
    X
    public class Solution {
        public List<Integer> rightSideView(TreeNode root) {
            List<Integer> ret = new ArrayList<Integer>();
            if(root == null) return ret;
            Queue<TreeNode> q = new LinkedList<TreeNode>();
            q.offer(root);
            while(!q.isEmpty()){
                int cnt = q.size();
                for(int i = 0;i < cnt;i++){
                    TreeNode cur = q.poll();
                    if(i == cnt-1){
                        ret.add(cur.val);
                    }
                    if(cur.left != null){
                        q.offer(cur.left);
                    } 
                    if(cur.right != null){
                        q.offer(cur.right);
                    } 
                }
            }
            return ret;
        }
    }

  • 0
    P

    My solution counting the number of remaining nodes at current level and the number of nodes being expanded at the next level. :)

    class Solution {
        public:
            vector<int> rightSideView(TreeNode *root) {
                vector<int> res;
                TreeNode *cur = root;
                if(!cur)
                    return res;
                queue<TreeNode*> q;
                q.push(cur);
                int level_n = 1, next_level_n = 0;               
                while(!q.empty()){
                    TreeNode *tmp = q.front();
                    q.pop();
                    if(tmp->left){
                        q.push(tmp->left);
                        ++next_level_n;
                    }
                    if(tmp->right){
                        q.push(tmp->right);
                        ++next_level_n;
                    }
                    --level_n;
                    if(level_n == 0){
                        res.push_back(tmp->val);
                        level_n = next_level_n;
                        next_level_n = 0;
                    }
                }
                return res;
            }
        };

  • 0
    Y

    My answer is exactly like yours, but it got MLE.


  • 0
    S

    Can you zo us?


Log in to reply
 

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