My C++ accepted O(n) solution with no record for the depth of a node


  • 0
    V

    I use an aux function which only return bool type and the depth will not be record.

    #include <algorithm>
        
        using std::max;
        
        class Solution {
        public:
            bool isBalanced(TreeNode *root) {
                int x = 0;
                return isBalancedAux(root, x);
            }
            
        private:
            bool isBalancedAux(TreeNode *root, int& depth) {
                if (root == NULL) { depth = 0; return true; }
                
                if (root->left == NULL && root->right == NULL) {
                    depth = 1;
                    return true;
                }
                
                int left_depth = 0, right_depth = 0;
                if (isBalancedAux(root->left, left_depth) && 
                    isBalancedAux(root->right, right_depth)) {
                    int distance = left_depth - right_depth;
                    if (-1 <= distance && distance <= 1) {
                        depth = max(left_depth, right_depth) + 1;
                        return true;
                    }
                }
                
                depth = max(left_depth, right_depth) + 1;
                return false;
            }
        };

  • 0
    R

    you don't really need if (root->left == NULL && root->right == NULL) { depth = 1; return true; }

    as it will be taken care by if (root == NULL) { depth = 0; return true; }


Log in to reply
 

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