A Solution by Recursively calculating tree height


  • 0
    L

    The first solution is to create a helper function to calculate height and pass bool value.

    public bool IsBalanced(TreeNode root) {
        int height = 0;
        return treeHeight(ref height, root);
    }
    private bool treeHeight(ref int height, TreeNode root){
        if (root == null) return true;
        int lHeight = height + 1, rHeight = height + 1;
        if (!treeHeight(ref lHeight, root.left) || !treeHeight(ref rHeight, root.right))
            return false;
        if (Math.Abs(lHeight - rHeight) > 1) return false;
        height = Math.Max(lHeight, rHeight);
        return true;
    }
    

    The 2nd solution is to create a helper function to calculate height only.

    public bool IsBalanced(TreeNode root) {
        if(root == null) return true;
        if(!IsBalanced(root.left) || !IsBalanced(root.right)) return false;
        if(Math.Abs(treeHeight(0, root.left) - treeHeight(0, root.right)) > 1) return false;
        return true;
    }
    
    private int treeHeight(int lastHeight, TreeNode root){
        if(root == null) return lastHeight;
        int leftHeight = treeHeight(lastHeight + 1, root.left);
        int rightHeight = treeHeight(lastHeight + 1, root.right);
        return Math.Max(leftHeight, rightHeight);
    }

Log in to reply
 

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