C++ Simple Solution, Concise Code, O(1) space with Morris Trv


  • 1

    Simple recursion traversal
    O(n) space;
    O(n) time;

    class Solution {
        void dfs(TreeNode* cur, int height, pair<int, int>& res) {
            if (!cur)
                return;
            if (height > res.second)
                res = {cur->val, height};
            dfs(cur->left, height + 1, res);
            dfs(cur->right, height + 1, res);
        }
    public:
        int findBottomLeftValue(TreeNode* root) {
            pair<int, int> res(0, -1);
            dfs(root, 0, res);
            return res.first;
        }
    };
    

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

    class Solution {
    public:
        int findBottomLeftValue(TreeNode* root) {
            int height = 0;
            pair<int, int> res = {0, -1};
            TreeNode* cur = root, *prev = nullptr;
            while (cur) {
                if (cur->left == nullptr) {
                    //
                    if (height > res.second)
                        res = {cur->val, height};
                    cur = cur->right;
                    height++;
                } else {
                    prev = cur->left;
                    int move = 1;
                    while (prev->right && prev->right != cur) {
                        prev = prev->right;
                        move++;
                    }
                    if (prev->right == nullptr) {
                        prev->right = cur;
                        //
                        if (height > res.second)
                            res = {cur->val, height};
                        cur = cur->left;
                        height++;
                    } else {
                        prev->right = NULL;
                        height -= move + 1;
                        cur = cur->right;
                        height++;
                    }
                        
                }
            }
            return res.first;
        }
    };
    

  • 0
    A

    @yong.cao.7731 You are not the really O(1) space, because you are using recursive function, of which space cost increases with the depth of path.


  • 0

    @ayanami98
    Hi, it is O(1) space for the second solution which use Morris Traversal.
    For the first solution, it does take O(n) space.


Log in to reply
 

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