C++ solution with breadth-first traveling


  • 0
    C
    struct Node {
        TreeNode* treeNode;
        int depth;
        Node(TreeNode* n, int d): treeNode(n), depth(d) { } 
    };
    
    class Solution {
    public:
        vector<int> rightSideView(TreeNode* root) {
            vector<int> result;
            if (!root) {
                return result;
            }
            map<int, int> m;
            queue<Node> q;
            q.push(Node(root, 0));
            while (!q.empty()) {
                Node n = q.front();
                q.pop();
                auto& v = m[n.depth];
                v = n.treeNode->val;
                if (n.treeNode->left) {
                    q.push(Node(n.treeNode->left, n.depth + 1));
                }
                if (n.treeNode->right) {
                    q.push(Node(n.treeNode->right, n.depth + 1));
                }
            }
            for (const auto& it: m) {
                result.push_back(it.second);
            }
            return result;
        }   
    };
    

  • 0
    C

    A slightly optimized one without map.

    struct Node {
        TreeNode* treeNode;
        int depth;
        Node(TreeNode* n, int d): treeNode(n), depth(d) { } 
    };
    
    class Solution {
    public:
        vector<int> rightSideView(TreeNode* root) {
            vector<int> result;
            if (!root) {
                return result;
            }
            queue<Node> q;
            q.push(Node(root, 0));
            while (!q.empty()) {
                Node n = q.front();
                q.pop();
                if (result.size() == n.depth) {
                    result.push_back(n.treeNode->val);
                } else {
                    result.back() = n.treeNode->val;
                }
                if (n.treeNode->left) {
                    q.push(Node(n.treeNode->left, n.depth + 1));
                }
                if (n.treeNode->right) {
                    q.push(Node(n.treeNode->right, n.depth + 1));
                }
            }
            return result;
        }   
    };
    

Log in to reply
 

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