Java simpler and better bottom up solution O(n)
Since the height of a tree is always greater than or equal to 0,\nWe use -1 as a flag to indicate if the subtree is not balanced.\nUse DFS (postorder) to scan t
Since the height of a tree is always greater than or equal to 0,\nWe use -1 as a flag to indicate if the subtree is not balanced.\nUse DFS (postorder) to scan the tree to avoid checking the height multiple times.\n\n```\nclass Solution {\n    public boolean isBalanced(TreeNode root) {\n        return getHeight(root) != -1;\n    }\n    \n    private int getHeight(TreeNode node) {\n        if (node == null) return 0;\n\n        int left = getHeight(node.left);\n        int right = getHeight(node.right);\n\n        // left, right subtree is unbalanced or cur tree is unbalanced\n        if (left == -1 || right == -1 || Math.abs(left - right) > 1) return -1;\n\n        return Math.max(left, right) + 1;\n    }\n}\n```\n\nTime: O(n)\nWe use DFS to scan the tree one time.\n\nSpace: O(n)\nThe call statck of the recursive getHeight function is equal to the height of the tree. \nIn the worst case the tree is totally skewed, height of the tree is equal to the number of nodes.
['Depth-First Search', 'Java']