C++ O(1) Space Recursion and Iterative Solution - Easy Understanding


  • 0
    Z

    Recursion:

    class Solution {
    public:
        vector<int> findMode(TreeNode* root) {
            int cur = INT_MAX, cur_max = 0, prev_max = 1; // This initialization can handle INT_MAX case
            vector<int> res;
            helper(root, cur, cur_max, prev_max, res); // In-order traversal
            if (cur_max > prev_max) return {cur};
            else if (cur_max == prev_max) res.push_back(cur);
            return res;
        }
    private:
        void helper(TreeNode *root, int &cur, int &cur_max, int &prev_max, vector<int> &res) {
            if (!root) return;
            helper(root->left, cur, cur_max, prev_max, res);
            if (root->val != cur) {
                if (cur_max > prev_max) {
                    prev_max = cur_max;
                    res = {cur};
                } else if (cur_max == prev_max) res.push_back(cur);
                cur_max = 1;
                cur = root->val;
            } else ++cur_max;
            helper(root->right, cur, cur_max, prev_max, res);
        }
    };
    

    Iterative:

    class Solution {
    public:
        vector<int> findMode(TreeNode *root) {
            int cur = INT_MAX, cur_max = 0, prev_max = 1;
            vector<int> res;
            stack<TreeNode *> st;
            TreeNode *node = root;
            while (!st.empty() || node) {
                if (!node) {
                    node = st.top();
                    st.pop();
                    if (node->val != cur) {
                        if (cur_max > prev_max) {
                            prev_max = cur_max;
                            res = {cur};
                        } else if (cur_max == prev_max) res.push_back(cur);
                        cur_max = 1;
                        cur = node->val;
                    } else ++cur_max;
                    node = node->right;
                }
                while (node) {
                    st.push(node);
                    node = node->left;
                }
            }
            if (cur_max > prev_max) return {cur};
            else if (cur_max == prev_max) res.push_back(cur);
            return res;
        }
    };
    

Log in to reply
 

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