Thinking process of bottom-up solution
From the recursive perspective, we know that we need to know 2 things: \n\n1. If left/right subtrees is balanced\n2. The height of left/right subtree\n\nThen I 
From the recursive perspective, we know that we need to know 2 things: \n```\n1. If left/right subtrees is balanced\n2. The height of left/right subtree\n```\nThen I think how can I get both of them? The only way to do it is: **return both of them in the  recursion function** i.e. `{height, isBalanced}`, rather than just return the `height` like the top-down solution. \nBut the problem is that `balanced` is `boolean` data type and `height` is an `int` data type. We cannot declare an array with different data type in Java(However Python can do it :P). So I use `int`as the replacement of `balanced` boolean data type: `-1` as `false`, `1` as `true`. Thus the result can be stored in the array `int[] cur = new int[2]`.\n\n```java\nclass Solution {\n    public boolean isBalanced(TreeNode root) {\n\t    // corner case\n        if(root == null) return true;\n        \n        int[] res = getHeight(root);\n        return res[1] == 1;\n    }\n    \n    // return [height, balanced]\n    public int[] getHeight(TreeNode root){\n        // base case\n        if(root == null) return new int[]{0, 1};\n        \n        int[] cur = new int[2];\n        \n        int[] left = getHeight(root.left);\n        if(left[1] == -1){\n            cur[1] = -1; // unbalanced, do not care about height anymore\n            return cur;\n        }\n        \n        int[] right = getHeight(root.right);\n        if(right[1] == -1){\n            cur[1] = -1; // unbalanced, do not care about height anymore\n            return cur;\n        }\n        \n        if(Math.abs(left[0] - right[0]) > 1){\n            cur[1] = -1; // unbalanced, do not care about height anymore\n            return cur;\n        }\n        \n\t\t// set [height, balanced]\n        cur[0] = Math.max(left[0], right[0]) + 1; // set height\n        cur[1] = 1; // set balanced\n        return cur;\n    }\n    \n}\n```\n\n---\n**Optimized**\n`{height, isBalanced}`\nBut notice that the height of a tree is **always** `>= 0`, and we do not care about the height when the subtree is already confirmed imbalanced. So we can use `-1` to represents `imbalanced`, then we can merge the `int` array of size 2 to just a `int` value to save some space. That\'s the magic!!!\n(But to be honest, who cares such little space. O(2) == O(1), the value is that if you are facmilar with this, you can directly use -1 which is easier to write)\n\nFinal code:\n\n```java\nclass Solution {\n    public boolean isBalanced(TreeNode root) {\n\t    // corner case\n        if(root == null) return true;\n        \n        return getHeight(root) != -1;\n    }\n    \n    // return the height of tree rooted at `root`if balanced, otherwise -1\n    public int getHeight(TreeNode root){\n        // base case\n        if(root == null) return 0;\n        \n        int left = getHeight(root.left);\n        if(left == -1) return -1;\n\n        int right = getHeight(root.right);\n        if(right == -1) return -1;\n        \n        if(Math.abs(left - right) > 1) return -1;\n        return Math.max(left, right) + 1;\n    }\n}\n```\n\ntime complexity: `O(n)`\nspace complexity: `O(height)`
[]