Clean java code with explanation


  • 1

    This solution summarized some good ideas of other solutions on the forum.
    It also corrected the misunderstanding of "depth of tree".
    isBalancedHelper returns the actual depth of tree if the tree is balanced, or -2 if unbalanced. Why -2? The depth of tree is defined as number of edges from root to its deepest leaf node. So if a node is null, its depth of -1, instead of 0. The root with no children has a depth of 0. it is calculated as max depth of its children, which is -1, plus 1. Therefore -1 is considered as a valid depth, while -2 is not. Once a subtree is found unbalanced, return -2 immediately to avoid useless computing. That is why leftDepth and rightDepth should not be calculated together and the comparision is done later, even tought the code would be cleaner in that way.

    public class Solution {
            public boolean isBalanced(TreeNode root) {
                return isBalancedHelper(root) >= -1 ? true : false;
            }
            
            private int isBalancedHelper(TreeNode root) {
                if (root == null)
                    return -1;
                int leftDepth = isBalancedHelper(root.left);
                if (leftDepth == -2)
                    return -2;
                int rightDepth = isBalancedHelper(root.right);
                if (rightDepth == -2)
                    return -2;
                return Math.abs(leftDepth - rightDepth) > 1 ? -2 :
                        Math.max(leftDepth, rightDepth) + 1;
            }
        }

Log in to reply
 

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