C++ Non-recursive O(n) time O(1) space solution, based on Morris Traversal


  • 0
    A

    210 / 210 test cases passed
    Status: Accepted
    Runtime: 3 ms

    class Solution {
    public:
        vector<int> rightSideView(TreeNode* root) {
            vector<int> v;
            if (!root) return v;
            uint k = 1, o = 0;
            while (root) {
                if (TreeNode *p = root->right) {
                    uint t = 1;
                    while (p->left && p->left != root) p = p->left, t++;
                    if (p->left) {
                        p->left = NULL;
                        k -= t;
                        root = root->left;
                    } else {
                        p->left = root;
                        if (k++ > o) v.push_back(root->val), o++;
                        root = root->right;
                    }
                } else {
                    if (k++ > o) v.push_back(root->val), o++;
                    root = root->left;
                }
            }
            return v;
        }
    };
    

Log in to reply
 

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