C++ storing depth O(n) complexity


  • 0
    C

    Many of the c++ solutions posted in the discussion forum has O(N^2) complexity. To reduce that an idea would be to store the depth information on stack.

    class Solution {
    private:
        inline bool balanced(TreeNode* root, int& dep) {
            if (!root) {
                dep = 0;
                return true;
            }
            int dep_left, dep_right = 0;
            if (balanced(root->left, dep_left) && balanced(root->right, dep_right)) {
                dep = dep_left > dep_right ? dep_left : dep_right;
                ++dep;
                return (dep_left - dep_right <= 1 && dep_left - dep_right >= -1);
            }
            return false;
        }
    public:
        bool isBalanced(TreeNode* root) {
            int dep;
            return balanced(root, dep);
        }
    };

Log in to reply
 

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