Balanced Binary tree


  • 0
    S
    class Solution {
        bool flag;
    public:
        bool isBalanced(TreeNode *root) {
    	flag=true;
    	if(checkbal(root)){
    		return flag;
    	}
        }
    
    	int checkbal(TreeNode *root){
    	    int x,y;
            if(root==NULL) return 1;
            x=checkbal(root->left);
            y=checkbal(root->right);
            if(x-y<=1 && x-y>=-1) {
                if(x>y) return x+1;
                else return y+1;
            }
            else{
             flag=false; 
             return 0;
            }
    	}
            
    };

  • 0
    S

    My answer is accepted.
    I am checking the height of both left and right subtrees. Whenever I find some subtree is not balanced I am keeping the flag to false.

    Can any one tell me is there any optimal solution than this.


  • 1
    H
    public class Solution {
        public boolean isBalanced(TreeNode root) {
            if(root==null)
            return true;
            
        if(height(root)==-1)
        return false;
        return true;
        }    
        public int height(TreeNode root){
            if(root==null)
            return 0;
            int left=height(root.left);
            int right=height(root.right);
            if(left==-1|| right==-1)
            return -1;
            if(Math.abs(left-right)>1)
            return -1;
            return Math.max(left,right)+1;
        
        }
    }

  • 0
    S

    Thanks for your post. However it would be better to elaborate thoughts first, then ask for better solution. Please read the FAQ (http://oj.leetcode.com/discuss/faq) for more info.


  • 0
    S

    Thanks for your post. However it would be better to share solution with elaborating thoughts. Please read the FAQ (http://oj.leetcode.com/discuss/faq) for more info.


Log in to reply
 

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