leetcode Question: Binary Tree Right Side View

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.

For example:
Given the following binary tree,

   1            <---
 /   \
2     3         <---
 \     \
  5     4       <---

You should return [1, 3, 4].

Analysis:

Note that in this problem, it is NOT to print out the right most sub tree.
It is to print out the most right element in each level.
Therefore the problem becomes pretty straightforward, which easily reminds us one of the basic tree operations:  level order traversal.

Similar to my previous post (here), we can use two queues to do the level order traversal. The only difference is in this question, we only need to store the 'last' element in each level and save it to the result vector. Implementation details can be seen in the following code.

Code(C++):

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector<int> rightSideView(TreeNode* root) {
        queue<TreeNode*> p, q;
        vector<int> res;
        if (!root) return res;
        
        p.push(root);
        while (1){
            int last;
            while (!p.empty()){
                TreeNode* cur = p.front();
                if (cur->left) q.push(cur->left);
                if (cur->right) q.push(cur->right);
                last = cur->val;
                p.pop();
            }
            res.push_back(last);
            p=q;
            while (!q.empty()){q.pop();}
            if (p.empty()) return res;
        }
    }
};

Code(Python):

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    # @param {TreeNode} root
    # @return {integer[]}
    def rightSideView(self, root):
        res = []
        if not root:
            return res
        p = []
        q = []
        p.append(root)
        while True:
            last = root.val
            while p:
                if p[0].left:
                    q.append(p[0].left)
                if p[0].right:
                    q.append(p[0].right)
                last = p[0].val
                p.pop(0);
            res.append(last)
            p = q
            q = []
            if not p:
                return res