C++ Simple Solution, Concise Code, Morris Traversal


  • 4

    Recursion
    O(n) space
    O(n) time

    class Solution {
        void dfs(TreeNode* cur, vector<int>& res, int height) {
            if (!cur)
                return;
            if (height >= res.size())
                res.push_back(cur->val);
            else
                res[height] = max(res[height], cur->val);
            dfs(cur->left, res, height + 1);
            dfs(cur->right, res, height + 1);
        }
    public:
        vector<int> largestValues(TreeNode* root) {
            vector<int> res;
            int height = 0;
            dfs(root, res, height);
            return res;
        }
    };
    

    Morris Traversal
    O(1) space
    O(n) time
    Morris Traversal
    Get Height by Morris Traversal

    class Solution {
    public:
        vector<int> largestValues(TreeNode* root) {
            vector<int> res;
            TreeNode* cur = root, *prev = NULL;
            int deep = 0;
            while (cur) {
                if (cur->left == NULL) {
                    //
                    if (deep >= res.size())
                        res.push_back(cur->val);
                    else
                        res[deep] = max(res[deep], cur->val);
                    cur = cur->right;
                    deep++;
                } else {
                    prev = cur->left;
                    int move = 1;
                    while (prev->right && prev->right != cur) {
                        prev = prev->right;
                        move++;
                    }
                    if (prev->right == NULL) {
                        if (deep >= res.size())
                            res.push_back(cur->val);
                        prev->right = cur;
                        cur = cur->left;
                        deep++;
                    } else {
                        // back to parent node, remove connection
                        prev->right = NULL;
                        deep -= move + 1;
                        //
                        if (deep >= res.size())
                            res.push_back(cur->val);
                        else
                            res[deep] = max(res[deep], cur->val);
                        cur = cur->right;
                        deep++;
                    }
                }
            }
            return res;
        }
    };
    

  • 0

    Ooh, keeping track of the depth like that in Morris traversal is very nice. I'd call it "O(1) extra space", the "O(n) space" doesn't do it justice.


  • 0

    @StefanPochmann Yeah, I typed O(n) by mistake. Thanks for your upvote. :)


  • 0
    M

    @StefanPochmann @yong-cao-7731 how is this O(1) space when the size of the returned vector is dependent on the height of the tree?


  • 0

    @Megziflips That's why I said "extra". As in "other than the result, since there's nothing that can be done about that".

    Although it's not quite right, since the result vector probably has linear extra capacity and also uses extra linear space when it runs out of capacity for a push_back and allocates new space and moves the old data over. Not sure why I didn't think of that back then. Maybe I was just too delighted with the algorithm.


  • 0
    M

    @StefanPochmann oh okay. Thanks for the feedback. That's understandable.


Log in to reply
 

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