Cpp O(1) space 2-passes inorder traverse


  • 0
    Z
    /**
     * Definition for a binary tree node.
     * struct TreeNode {
     *     int val;
     *     TreeNode *left;
     *     TreeNode *right;
     *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
     * };
     */
    #include <algorithm>
    #include <limits>
    #include <vector>
    class Solution {
        std::vector<int> mode;
        int max_cnt = std::numeric_limits<int>::lowest();
        int cur = max_cnt;
        int cur_cnt = 0;
    public:
        void inorder_traverse(TreeNode *root, bool collect) {
            if (root->left != NULL) {
                inorder_traverse(root->left, collect);
            }
            if (root->val == cur) {
                ++cur_cnt;
            } else {
                if (collect) {
                    if (cur_cnt == max_cnt) {
                        mode.push_back(cur);
                    }
                } else {
                    max_cnt = std::max(cur_cnt, max_cnt);
                }
                cur = root->val;
                cur_cnt = 1;
            }
            if (root->right != NULL) {
                inorder_traverse(root->right, collect);
            }
        }
        vector<int> findMode(TreeNode* root) {
            if (root == NULL) {
                return mode;
            }
            inorder_traverse(root, false);
            max_cnt = std::max(cur_cnt, max_cnt);
            cur = max_cnt;
            cur_cnt = 0;
            inorder_traverse(root, true);
            if (cur_cnt == max_cnt) {
                mode.push_back(cur);
            }
            return  mode;
        }
    };
    

Log in to reply
 

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