解法一：From top to bottom

1 int treeHeight(TreeNode *T) 2 { 3     if (T == NULL) 4         return 0; 5      6     return max(treeHeight(T->left), treeHeight(T->right)) + 1; 7 } 8  9 bool isBalanced(TreeNode* root)10 {11     if (root == NULL)12         return true;13 14     int left_height = treeHeight(root->left);15     int right_height = treeHeight(root->right);16     if (abs(left_height - right_height) > 1)17         return false;18 19     if (!isBalanced(root->left) || !isBalanced(root->right))20         return false;21 22     return true;23 }

解法一递归判断子树是否为平衡二叉树的过程中，重复计算了多次子树的高度，时间复杂度大于O(N)。解法二将这个计算过程优化了，时间复杂度为O(N)。

解法二：From bottom to top

1 int dfsTreeHeight(TreeNode *T) 2 { 3     if (T == NULL) 4         return 0; 5  6     int left_height = dfsTreeHeight(T->left); 7     if (left_height == -1) 8         return -1; 9     int right_height = dfsTreeHeight(T->right);10     if (right_height == -1)11         return -1;12     if (abs(left_height - right_height) > 1)13         return -1;14 15     return max(left_height, right_height) + 1;16 }17 18 bool isBalanced(TreeNode* root)19 {20     if (root == NULL)21         return true;22 23     return dfsTreeHeight(root) != -1;24 }