Accepted O(n) solution


  • 20
    Z

    We determine recursively the height of the root node but when the recursion is coming upwards we return UNBALANCED instead of the actual height if we know that the tree is already known to be unbalanced.

    We visit each node just once thus it has linear time complexity.

    private static final int UNBALANCED = -99;
    
    public boolean isBalanced(TreeNode root) {
        if (root == null) {
            return true;
        }
        return getHeight(root) != UNBALANCED;
    }
    
    private int getHeight(TreeNode root) {
        if (root == null) {
            return -1;
        }
        int l = getHeight(root.left);
        int r = getHeight(root.right);
        if (l == UNBALANCED || r == UNBALANCED || Math.abs(l-r) > 1) {
            return UNBALANCED;
        }
        return 1 + Math.max(l,r);
    }

  • 0
    J

    I think it's better to record the height in TreeNode.val if the node can be modified. Recursion will take many duplicate calculations !


  • 0
    G
    /**
     * Definition for binary tree
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode(int x) { val = x; }
     * }
     */
    public class Solution {
        public boolean isBalanced(TreeNode root) {
            if (depth(root,0) == Integer.MAX_VALUE) return false;
            else return true;
        }
        
        
        private int depth(TreeNode root, int depth) {
            if (root == null) return depth;
            
            int depthLeft = depth(root.left, depth+1);
            int depthRight = depth(root.right, depth+1);
    
            if (Math.abs(depthLeft - depthRight) > 1) 
                return Integer.MAX_VALUE;
            
            int maxDepth = Math.max(depthLeft,depthRight);
                        
            return maxDepth;
        }
    
    }
    

    My approach is similar. take a look.


  • 0
    L

    It's a great idea to encode both the balance and height information into one field. I have a sort of orthodox approach though.

        /** 
         *  carry both the balance and height information
         */
        private class BalanceResult {
        	boolean isBalanced; 
        	int size;
        	
        	BalanceResult(boolean b, int s){
        		isBalanced = b;
        		size = s;
        	}
        }
        
        private BalanceResult isBalanced_rec(TreeNode root){
        	if(root == null){
        		return new BalanceResult(true, 0);
        	}
        	
        	BalanceResult left = isBalanced_rec(root.left);
        	BalanceResult right = isBalanced_rec(root.right);
        
        	if(!left.isBalanced || !right.isBalanced){
        		return new BalanceResult(false, -1);
        	}else{
        		if(Math.abs(left.size - right.size) > 1){
        			return new BalanceResult(false, -1);
        		}else{
        			int newSize = Math.max(left.size, right.size)+1;
        			return new BalanceResult(true, newSize);
        		}
        	}
        }
        
        public boolean isBalanced(TreeNode root) {
        	return isBalanced_rec(root).isBalanced;
        }
    

  • 0
    D

    There is no duplicated calculation in this solution.


  • 0
    W
    This post is deleted!

  • 0
    Z

    It visits each node just once hence the linear time complexity.

    Even if you don't understand what the code does just notice that the only place where recursion happens is at:

    int l = getHeight(root.left);
    int r = getHeight(root.right);
    

    thus we will never visit the same node twice.


  • 0
    C

    Thank you!
    I took your solution and wrote it in C, and went from my first try 15ms, to your solution 8ms.


  • 0
    S

    class Solution {
    public:
    bool isBalanced(TreeNode* root) {
    int height;
    return isBalanced1(root,height);
    }
    bool isBalanced1(TreeNode* root,int &height) {
    if(root==NULL)
    {
    height=0;
    return true;
    }
    bool left=true,right=true;
    int leftheight,rightheight;
    left=isBalanced1(root->left,leftheight);
    if(left)
    {
    right=isBalanced1(root->right,rightheight);
    }
    height=max(leftheight,rightheight)+1;
    return left&&right&&(abs(leftheight-rightheight)<=1);
    }
    };


  • 0
    S

    @sun5-0 my code runtime is 6ms.


  • 0
    G

    A good Intuitive and practical solution... better than above ones


Log in to reply
 

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