The bottom up O(N) solution would be better


  • 0
    M

    It seems we should definitely use the bottom up approach

    Additionally, in the first approach(Top down), I think we can add a hash map(unordered_map<TreeNode*, int> depth) to record the depth of the subtree of a node, to avoid repeated computation. Then we can reduce the average time complexity.


  • 0

    My accepted 9ms solution, similar to your second method:

    
    class Solution {
    	int isBalanced(TreeNode* root, bool &balanced)
    	{
    		if (root == nullptr)
    		{
    			balanced = balanced && true;
    			return 0;
    		}
    		int d1 = isBalanced(root->left, balanced);
    		int d2 = isBalanced(root->right, balanced);
    		balanced = balanced && abs(d1 - d2) <= 1;
    		return 1 + max(d1, d2);
    	}
    public:
    	bool isBalanced(TreeNode* root) 
    	{
    		bool balanced = true;
    		isBalanced(root, balanced);
    		return balanced;
    	}
    };

  • 1
    2

    @yangleizou

    I think it should be O(nlogn) in average case, and O(n^2) in worse case.


  • 0
    G

    It's always fun to see that someone else came up with (roughly) the same algorithm!

    Here's my version:

    class Solution {
    public:
        bool isBalanced(TreeNode* root) {
            return work(root, 0) != -1;
        }
        
        int work(TreeNode* node, int d) {
            if (!node) return d;
            
            int a = work(node->left, d+1);
            int b = work(node->right, d+1);
            
            return abs(a - b) <= 1 ? max(a, b) : -1;
        }
    };
    

    Note the return statement's conditional. (Try working out the possible values for a and b to prove its correctness).


  • 0
    L
     bool isBalanced(TreeNode* root) {
            if (root==nullptr)
                return true;
            if (abs((Deepth(root->left)-Deepth(root->right))<=1)
                return isBalanced(root->left)&&isBalanced(root->right);
            else
                return false;
        }
        int Deepth(TreeNode* root) {
            if (root = nullptr)
                return 0;
            return max(1+Deepth(root->left),1+Deepth(root->right));
        }
    

  • 0
    S

    Same ideas here. Basically, we can check the height while we are computing the node's height.

    // O(n) time, O(H) space.
    public:
        bool isBalanced(TreeNode* root) {
            return checkHeight(root) != -1;
        }
    private:
        int checkHeight(TreeNode* root) {
            if ( root == nullptr ) return 0;
            int left = checkHeight(root->left);
            if ( left == -1 ) return -1;
            int right = checkHeight(root->right);
            if ( right == -1 ) return -1;
            
            if (abs(left - right) > 1) return -1;
            else return max(left, right) + 1;
        }
    

  • 0
    L

    Time: O(n), Space: O(height) Iterative Solution

    // Method 2: Iterative Solution (Post-order Traversal)
    // Time: O(n)
    // Space: O(height)
    boolean isBalanced(TreeNode root) {
      if(root == null) {
        return true;
      }
    
      Deque<Integer> heights = new LinkedList<>();
      Deque<TreeNode> stack = new LinkedList<>();
      stack.offerLast(root);
    
      //set to root not null to not confuse when root is misisng children
      TreeNode prev = root;
    
      while(!stack.isEmpty()) {
        //get the next node to process, peek because we need to maintain trail until we return
        TreeNode curr = stack.peekLast();
    
        //if we just returned from left child
        if (prev == curr.left) {
          if (curr.right != null) {
            //if we can go right go
            stack.offerLast(curr.right);
          } else {
            //otherwise right height is -1 does not exist and combine heights
            heights.offerLast(0);
            if (!combineHeights(heights)) {
              return false;
            }
            stack.pollLast(); //back to parent
          }
        } else if (curr.right == prev) { //if we just returned from right child
          if (!combineHeights(heights)) {
            return false;
          }
          stack.pollLast(); //up to parent
        } else {
          //this came from a parent, first thing is to visit the left child, or right if no left
          if (curr.left != null) {
            stack.offerLast(curr.left);
          } else {
            if (curr.right != null) {
              //no left so when we combine this node left is 0
              heights.offerLast(0);
              //since we never go left above logic does not go right, so we must here
              stack.offerLast(curr.right);
            } else {
              //no children set height to 1
              heights.offerLast(1);
              stack.pollLast(); //back to parent
            }
          }
        }
    
        prev = curr;
      }
    
      return true;
    }
    
    // Helper function: combineHeights
    // pop both previous heights and make sure they are balanced, 
    // if not return false, if so return true and push the greater + 1
    private boolean combineHeights(Deque<Integer> heights) {
      int rightHeight = heights.pollLast();
      int leftHeight = heights.pollLast();
    
      if(Math.abs(leftHeight - rightHeight) > 1) {
        return false;
      } else {
        heights.offerLast(Math.max(leftHeight, rightHeight) + 1);
        return true;
      }
    }
    

  • 0
    K

    @VV_Driven n*log(n) is the mean Time complexity. and the worst comlexity is T(n)=T(n-1)+1...O(n^2)


Log in to reply
 

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